Бойер-Мур-Хорспул алгоритмі: Ішіндегі жолдарды іздеу
Boyer–Moore–Horspool algorithm
Boyer–Moore–Horspool алгоритмі: жолдардағы кіші жолдарды іздеуге арналған жылдам әдіс. Орташа жағдайда O(n) тиімділігі, ең жаманы – O(nm). Компьютер ғылымында қолданылады.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Компьютерлік ғылымда Бойер–Мур–Хорспул алгоритмі немесе Хорспул алгоритмі – тізбектердегі кіші тізбелерді табуға арналған алгоритм. Оны Найджел Хорспул 1980 жылы SBM деп жариялаған. Бұл Кнут–Моррис–Пратт алгоритмімен байланысты Бойер–Мур тізбегін іздеу алгоритмінің жеңілдетілген нұсқасы. Алгоритм орташа жағдайда кездейсоқ мәтінде O(n) күрделілігін алу үшін жадты уақытпен алмастырады, бірақ ең жаман жағдайда O(nm) болады, мұнда үлгінің ұзындығы m, ал ізделінетін тізбектің ұзындығы n.
In computer science, the Boyer–Moore–Horspool algorithm or Horspool's algorithm is an algorithm for finding substrings in strings. It was published by Nigel Horspool in 1980 as SBM. It is a simplification of the Boyer–Moore string search algorithm which is related to the Knuth–Morris–Pratt algorithm. The algorithm trades space for time in order to obtain an average case complexity of O(n) on random text, although it has O(nm) in the worst case, where the length of the pattern is m and the length of the search string is n.
Өнер көрсету
Алгоритм ұзын ине тізбектерімен ең жақсы жұмыс істейді, егер ол ағымдағы позициядағы мақта үйірінің соңғы байтын немесе оған жақын байтты сәйкес келмейтін символмен тұрақты түрде кездестірсе және иненің соңғы байты ине ішінде басқа жерде кездеспесе. Мысалы, "z" әрпімен аяқталатын 32 байтты ине, "z" байты жоқ 255 байтты мақта үйірін іздесе, 224 байтқа дейін салыстыру қажет болады. Ең жақсы жағдай үлкен O белгісінде Бойер-Мур тізбектік іздеу алгоритміне ұқсас, бірақ инициализацияның тұрақты қосымша шығындары және әрбір цикл үшін жұмсалатын уақыт аз. Ең нашар жағдай, жаман символдың жылжуы үнемі төмен болғанда (төменгі шегі 1 байттық жылжу) және иненің үлкен бөлігі мақта үйірімен сәйкес келгенде пайда болады. Жаман символдың жылжуы тек жартылай сәйкес келген жағдайда төмен болады, егер инедегі соңғы символ ине ішінде басқа жерде де кездессе, ал бір байттық жылжу соңғы екі позициядағы байттар бірдей болғанда болады. Жоғарыдағы "ең жақсы" жағдайға ұқсас канондық дегенеративті жағдай – 'a' байтынан кейін 31 'z' байтынан тұратын ине, ал мақта үйірі 255 'z' байтынан тұрады. Бұл 31 сәтті байт салыстыруын, сәтсіз аяқталатын 1 байт салыстыруын және содан кейін 1 байтты алға жылжытуды қамтиды. Бұл процесс тағы 223 рет қайталанады (255 – 32), жалпы байт салыстырулар саны 7168 (32 × 224) құрайды. (Байт салыстырудың басқа циклы басқаша әрекет етеді.) Ең нашар жағдай Бойер-Мур тізбектік іздеу алгоритміне қарағанда айтарлықтай жоғары, бірақ бұл қалыпты жағдайларда қол жеткізу қиын. Сондай-ақ, бұл ең нашар жағдай наивті (бірақ әдеттегі) memcmp алгоритмі үшін де ең нашар жағдай екенін атап өткен жөн, бірақ оның іске асырылуы айтарлықтай оңтайландырылған (және кэш үшін ыңғайлы).
The algorithm performs best with long needle strings, when it consistently hits a non matching character at or near the final byte of the current position in the haystack and the final byte of the needle does not occur elsewhere within the needle. For instance a 32 byte needle ending in "z" searching through a 255 byte haystack which does not have a 'z' byte in it would take up to 224 byte comparisons. The best case is the same as for the Boyer–Moore string search algorithm in big O notation, although the constant overhead of initialization and for each loop is less. The worst case behavior happens when the bad character skip is consistently low (with the lower limit of 1 byte movement) and a large portion of the needle matches the haystack. The bad character skip is only low, on a partial match, when the final character of the needle also occurs elsewhere within the needle, with 1 byte movement happening when the same byte is in both of the last two positions. The canonical degenerate case similar to the above "best" case is a needle of an 'a' byte followed by 31 'z' bytes in a haystack consisting of 255 'z' bytes. This will do 31 successful byte comparisons, a 1 byte comparison that fails and then move forward 1 byte. This process will repeat 223 more times (255 − 32), bringing the total byte comparisons to 7,168 (32 × 224). (A different byte comparison loop will have a different behavior.) The worst case is significantly higher than for the Boyer–Moore string search algorithm, although obviously this is hard to achieve in normal use cases. It is also worth noting that this worst case is also the worst case for the naive (but usual) memcmp algorithm, although the implementation of that tends to be significantly optimized (and is more cache friendly).