Кіріспе
Жолды іздеу алгоритмі
Компьютер ғылымында Рабин–Карп алгоритмі немесе Карп–Рабин алгоритмі – мәтіндегі үлгілік жолдың нақты сәйкестігін табу үшін хэш қолданатын жол іздеу алгоритмі. Бұл алгоритм мәтіннің үлгіге сәйкес келмейтін орналасуын жылдам сүзу үшін жылмалы хэшті пайдаланады, содан кейін қалған орналасуларда сәйкестікті тексереді. Осы идеяның жалпыламасы бір үлгіге бірнеше сәйкестікті табуға немесе бірнеше үлгіге сәйкес келетін сәйкестіктерді табуға қолданылуы мүмкін. Бір үлгіге бір ғана сәйкестікті табу үшін алгоритмнің күтілетін уақыты үлгі мен мәтіннің біріктірілген ұзындығына пропорционалды, бірақ ең нашар жағдайдағы уақыт күрделілігі екі ұзындықтың көбейтіндісін құрайды. Көптеген сәйкестіктерді табу үшін күтілетін уақыт кіріс ұзындықтарына пропорционалды, сонымен қатар барлық сәйкестіктердің біріктірілген ұзындығы пропорционалдықтан асатын болуы мүмкін. Алайда, Aho–Corasick алгоритмі нашар жағдайда бірнеше үлгілердің барлық сәйкестіктерін кіріс ұзындығы мен сәйкестіктер санына пропорционалды уақыт пен кеңістікте таба алады (сәйкестіктердің жалпы ұзындығының орнына). Алгоритмнің практикалық қолданылуы – плагиатты анықтау. Алгоритм бастапқы материалды ескере отырып, мәтіннен сөйлемдердің мысалдарын жылдам іздей алады, әріптердің регистрі мен тыныш белгілер сияқты егжей-тегжейлі мәліметтерді елемейді. Ізделінетін жолдардың көптігіне байланысты, жалғыз жолды іздеу алгоритмдері тиімсіз болады.
although its worst case time complexity is the product of the two lengths. To find multiple matches, the expected time is linear in the input lengths, plus the combined length of all the matches, which could be greater than linear. In contrast, the Aho–Corasick algorithm can find all matches of multiple patterns in worst case time and space linear in the input length and the number of matches (instead of the total length of the matches). A practical application of the algorithm is detecting plagiarism. Given source material, the algorithm can rapidly search through a paper for instances of sentences from the source material, ignoring details such as case and punctuation. Because of the abundance of the sought strings, single string searching algorithms are impractical.
Шолу
Наивті тізбектерді салыстыру алгоритмі берілген үлгіні берілген мәтіннің барлық позицияларымен салыстырады. Әр салыстыруға үлгінің ұзындығына пропорционалды уақыт жұмсалады, ал позициялардың саны мәтіннің ұзындығына пропорционалды. Сондықтан, мұндай әдістің ең нашар жағдайдағы уақыты екі ұзындықтың көбейтіндісіне пропорционалды. Көптеген практикалық жағдайларда, сәйкессіздік анықталғанда әр позициядағы салыстыруды тоқтату арқылы бұл уақытты айтарлықтай қысқартуға болады, бірақ бұл идея жылдамдықтың кез келген деңгейде қамтамасыз етпейді. Бірнеше тізбектерді салыстыру алгоритмдері, соның ішінде Кнут-Моррис-Пратт алгоритмі және Бойер-Мур тізбегін іздеу алгоритмі, әр сәйкессіздіктен көбірек ақпарат алып, мәтіннің үлгіге сәйкес келмейтін позицияларын өткіріп жіберуге мүмкіндік бере отырып, тізбектерді салыстырудың ең нашар жағдайдағы уақытын азайтады. Рабин-Карп алгоритмі керісінше, әр позиция үшін жылдам шамамен тексеру үшін хэш-функцияны пайдаланып жылдамдығын арттырады, содан кейін осы шамамен тексеруден өткен позицияларда ғана нақты салыстыру жүргізеді. Хэш-функция – әрбір тізбекті сандық мәнге, яғни оның хэш-мәніне айналдыратын функция; мысалы, hash("сәлем") = 5 болуы мүмкін. Егер екі тізбек тең болса, олардың хэш-мәндері де тең болады. Жақсы жасалған хэш-функция үшін керісі де шамамен дұрыс: тең емес тізбектерде тең хэш-мәндері болуы өте сирек. Рабин-Карп алгоритмі мәтіннің әр позициясында сол позициядан басталатын және үлгінің ұзындығымен бірдей тізбектің хэш-мәнін есептейді. Егер бұл хэш-мәні үлгінің хэш-мәніне тең болса, ол сол позицияда толық салыстыру жүргізеді. Бұл жақсы жұмыс істеуі үшін хэш-функцияны көптеген жалған оң нәтижелер беретін хэш-функциялар тобынан кездейсоқ таңдау керек, яғни мәтіннің позициялары үлгімен бірдей хэш-мәніне ие, бірақ шын мәнінде үлгіге сәйкес келмейді. Бұл позициялар сәйкестік тудырмай, алгоритмнің жұмыс уақытын қажетсіз ұзартады. Сонымен қатар, қолданылатын хэш-функция жылдам жаңартылатын хэш-функция болуы керек, яғни мәтіннің әр позициясынан келесі позицияға хэш-мәнін жылдам жаңартуға болады. Әр позицияда хэш-функцияны бастапқы күйінен қайта есептеу тым баяу болады.
and the number of positions is proportional to the length of the text. Therefore, the worst case time for such a method is proportional to the product of the two lengths. In many practical cases, this time can be significantly reduced by cutting short the comparison at each position as soon as a mismatch is found, but this idea cannot guarantee any speedup. Several string matching algorithms, including the Knuth–Morris–Pratt algorithm and the Boyer–Moore string search algorithm, reduce the worst case time for string matching by extracting more information from each mismatch, allowing them to skip over positions of the text that are guaranteed not to match the pattern. The Rabin–Karp algorithm instead achieves its speedup by using a hash function to quickly perform an approximate check for each position, and then only performing an exact comparison at the positions that pass this approximate check. A hash function is a function which converts every string into a numeric value, called its hash value; for example, we might have hash("hello")=5. If two strings are equal, their hash values are also equal. For a well designed hash function, the inverse is true, in an approximate sense: strings that are unequal are very unlikely to have equal hash values. The Rabin–Karp algorithm proceeds by computing, at each position of the text, the hash value of a string starting at that position with the same length as the pattern. If this hash value equals the hash value of the pattern, it performs a full comparison at that position. In order for this to work well, the hash function should be selected randomly from a family of hash functions that are unlikely to produce many false positives, that is, positions of the text which have the same hash value as the pattern but do not actually match the pattern. These positions contribute to the running time of the algorithm unnecessarily, without producing a match. Additionally, the hash function used should be a rolling hash, a hash function whose value can be quickly updated from each position of the text to the next. Recomputing the hash function from scratch at each position would be too slow.