A searching method of the most similar string in the file of a document retrieval system

✍ Scribed by Kiyohiro Kobayashi; Tsuguyasu Imamura; Masashi Takahashi; Fumiko Kubota; Taiho Kanaoka; Yoshihiko Hamamoto; Shingo Tomita

• Publisher: John Wiley and Sons
• Year: 1992
• Tongue: English
• Weight: 916 KB
• Volume: 23
• Category: Article
• ISSN: 0882-1666
• DOI: 10.1002/scj.4690230203

✦ Synopsis

Abstract

To obtain a required document from the uncertain string information inputted by the user in a document retrieval system or an electronic filing system, the string most similar to the inputted string must be searched.

This paper assumes the most general case, where no constraint is imposed on the input error and discusses the efficient method of search for the string in the file which is the most similar to the inputted string. The tree structure is considered to be data structure. The string in the file corresponds to the leaf of the tree. Other vertices of the tree correspond to a string constructed from the set of strings below those vertices as a representative element.

The classification of the set of strings is made based on the similarity between strings. A simulation is executed using 100 to 1000 English words as the strings in the file. The search probability of the string most similar to the input string, as well as the search efficiency based on the number of similarity calculations, are examined to evaluate the usefulness of the proposed method.