Skip navigation
Please use this identifier to cite or link to this item:
Title: A searching algorithm for text with mistakes
Authors: Nasr S.
German, O. V.
Герман, О. В.
Keywords: публикации ученых
searching algorithm
text processing
finding text with mistakes
fuzzy Boyer–Moore method
metrics of similarity
Issue Date: 2020
Publisher: БГУИР
Citation: Nasr, S. A searching algorithm for text with mistakes / Nasr S., German O. V. // Доклады БГУИР. – 2020. – № 18 (1). – С. 29 – 34. –
Abstract: 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.
Appears in Collections:№18 (1)

Files in This Item:
File Description SizeFormat 
Nasr_A.pdf477,18 kBAdobe PDFView/Open
Show full item record

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.