Preview

Доклады БГУИР

Расширенный поиск

A SEARCHING ALGORITHM FOR TEXT WITH MISTAKES

https://doi.org/10.35596/1729-7648-2020-18-1-29-34

Полный текст:

Аннотация

The paper contains a new text searching method representing modification of the Boyer-Moore algorithm and enabling a user to find the places in the text where the given substring occurs maybe with possible errors, that is the string in text and a query may not coincide but nevertheless are identical. The idea consists in division of the searching process in two phases: at the first phase a fuzzy variant of the Boyer–Moore algorithm is performed; at the second phase the Dice metrics is used. The advantage of suggested technique in comparison with the known methods using the fixed value of the mistakes number is that it 1) does not perform precomputation of the auxiliary table of the sizes comparable to the original text sizes and 2) it more flexibly catches the semantics of the erroneous text substrings even for a big number of mistakes. This circumstance extends possibilities of the Boyer–Moore method by addmitting a bigger amount of possible mistakes in text and preserving text semantics. The suggested method provides also more accurate regulation of the upper boundary for the text mistakes which differs it from the known methods with fixed value of the maximum number of mistakes not depending on the text sizes. Moreover, this upper boundary is defined as Levenshtein distance not suitable for evaluating a relevance of the founded text and a query, while the Dice metrics provides such a relevance. In fact, if maximum Levenshtein distanse is 3 then how one can judge if this value is big or small to provide relevance of the search results. Consequently, the suggested method is more flexible, enables one to find relevant answers even in case of a big number of mistakes in text. The efficiency of the suggested method in the worst case is O(nc) with constant c defining the biggest allowable number of mistakes.

Об авторах

S. Nasr
The Belarussian State University of Informatics and RadioElectronics
Беларусь

Sara Nasr, PG student of Information Technologies in Automatized Systems Department



O. V. German
The Belarussian State University of Informatics and RadioElectronics
Беларусь

German Oleg Vitoldovich, PhD, Associate Professor of the Information Technologies in Automatized Systems Department

220600, Minsk, P. Brovki str. 6, +375-29-612-42-32



Список литературы

1. Manning Ch. D., Raghavan P., Schutze H. An introduction to information retrieval. Cambridge University Press; 2009.

2. Wu S., Manber U. Fast text searching allowing errors. Communication of the ACM. 2001;35:83-91.

3. Gusfield D. Algorithms on strings, trees and sequences. Computer science and computational biology. Cambridge university press; 1997.

4. Galil Z., Giancarlo R. Data structures and algorithms for approximate string matching. Journal of Complexity. 1988;4:33-72.

5. Gonnet G.H., Baeza-Yates R.A. Handbook of algorithms and data structures. Addison-Wesley. 1991.

6. Mandel I. [Cluster analysis]. M.: Finansy i statistika; 1988. (In Russ.)

7. Gourine N.I., German O.V. [Intelligent query analyzer to knowledge base of the multimedia electronic tutorial]. Trudy BGTU=Proceedings of BSTU. 2010;18(6):167-170. (In Russ.)


Для цитирования:


Nasr S., German O.V. A SEARCHING ALGORITHM FOR TEXT WITH MISTAKES. Доклады БГУИР. 2020;18(1):29-34. https://doi.org/10.35596/1729-7648-2020-18-1-29-34

For citation:


Nasr S., German O.V. A SEARCHING ALGORITHM FOR TEXT WITH MISTAKES. Doklady BGUIR. 2020;18(1):29-34. https://doi.org/10.35596/1729-7648-2020-18-1-29-34

Просмотров: 66


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1729-7648 (Print)
ISSN 2708-0382 (Online)