Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Жолдарды іздеу алгоритмі, Бойер-Мур теоремасы
String searching algorithm
the Boyer–Moore theorem prover
Компьютер ғылымында Бойер-Мур жолдарды іздеу алгоритмі – бұл тиімді жолдарды іздеу алгоритмі, ол практикалық жолдарды іздеу әдебиетінің стандартты өлшемі болып табылады. Оны 1977 жылы Роберт С. Бойер және Дж. Стротер Мур жасаған. Алғашқы мақалада үлгіні есептеу үшін статикалық кестелер болған, оларды қалай жасау керектігі түсіндірілмеген. Кестелерді жасау алгоритмі кейін жарияланды; бұл мақалада қателер болды, оларды кейіннен Войцех Риттер 1980 жылы түзеді. Алгоритм ізделіп жатқан жолды (үлгіні) алдын ала өңдейді, бірақ іздеу жүргізіліп жатқан жолды (мәтінді) емес. Сондықтан бұл модель мәтіннен әлдеқайда қысқа немесе бірнеше іздеулерде сақталатын қолданбалар үшін өте қолайлы. Бойер-Мур алгоритмі мәтіннің бөліктерін өткіріп жіберу үшін алдын ала өңдеу кезеңінде жиналған ақпаратты пайдаланады, нәтижесінде көптеген басқа жолдарды іздеу алгоритмдерінен төмен тұрақты коэффициент шығады. Жалпы, үлгінің ұзындығы артқан сайын алгоритм жылдамырақ жұмыс істейді. Алгоритмнің негізгі ерекшеліктері – жолдың басы емес, соңымен сәйкестіру және мәтіндегі әрбір таңбаны іздеудің орнына бірнеше таңбамен секіру арқылы мәтінді өткіріп жіберу.
In computer science, the Boyer–Moore string search algorithm is an efficient string searching algorithm that is the standard benchmark for practical string search literature. It was developed by Robert S. Boyer and J Strother Moore in 1977. The original paper contained static tables for computing the pattern shifts without an explanation of how to produce them. The algorithm for producing the tables was published in a follow on paper; this paper contained errors which were later corrected by Wojciech Rytter in 1980. The algorithm preprocesses the string being searched for (the pattern), but not the string being searched in (the text). It is thus well suited for applications in which the pattern is much shorter than the text or where it persists across multiple searches. The Boyer–Moore algorithm uses information gathered during the preprocess step to skip sections of the text, resulting in a lower constant factor than many other string search algorithms. In general, the algorithm runs faster as the pattern length increases. The key features of the algorithm are to match on the tail of the pattern rather than the head, and to skip along the text in jumps of multiple characters rather than searching every single character in the text.
Өнер көрсету
Бастапқы мақалада ұсынылған Бойер-Мур алгоритмі тек үлгі мәтінде кездеспесе ғана O(n+m) ең нашар жағдайда жұмыс істеу уақытына ие. Бұл алғаш рет 1977 жылы Кнут, Моррис және Пратт дәлелдеді, ең нашар жағдайда 5n салыстырудың жоғарғы шегімен. Ричард Коул 1991 жылы ең нашар жағдайда 3n салыстырудың жоғарғы шегімен дәлелдеу ұсынды. Егер үлгі мәтінде кездессе, бастапқы алгоритмнің жұмыс уақыты ең нашар жағдайда O(nm) болады. Бұл үлгі мен мәтін тек бір қайталап тұратын символдан тұратын кезде көру оңай. Дегенмен, Галиль ережесін қосу барлық жағдайларда сызықтық жұмыс уақытын қамтамасыз етеді.
The Boyer–Moore algorithm as presented in the original paper has worst case running time of O(n+m) only if the pattern does not appear in the text. This was first proved by Knuth, Morris, and Pratt in 1977, with an upper bound of 5n comparisons in the worst case. Richard Cole gave a proof with an upper bound of 3n comparisons in the worst case in 1991. When the pattern does occur in the text, running time of the original algorithm is O(nm) in the worst case. This is easy to see when both pattern and text consist solely of the same repeated character. However, inclusion of the Galil rule results in linear runtime across all cases.
Нұсқалар
Бойер-Мур-Хорспул алгоритмі – жаман символ ережесін ғана қолдана отырып, Бойер-Мур алгоритмінің жеңілдетілген түрі. Apostolico-Giancarlo алгоритмі берілген қатарласуда сәйкестік болды ма, жоқ па, тексеру процесін жылдамдатады. Бұл үлгіні алдын ала өңдеу кезінде алынған ақпаратты, әр сәйкестік әрекеті кезінде тіркелген жұрнақ сәйкестіктерінің ұзындығымен бірге пайдаланады. Жұрнақ сәйкестіктерінің ұзындығын сақтау үшін ізделіп жатқан мәтінмен бірдей өлшемдегі қосымша кесте қажет. Raita алгоритмі Бойер-Мур-Хорспул алгоритмінің өнімділігін жақсартады. Белгілі бір кіші жолдың берілген жолдағы іздеу үлгісі Бойер-Мур-Хорспул алгоритмінен өзгеше.
The Boyer–Moore–Horspool algorithm is a simplification of the Boyer–Moore algorithm using only the bad character rule. The Apostolico–Giancarlo algorithm speeds up the process of checking whether a match has occurred at the given alignment by skipping explicit character comparisons. This uses information gleaned during the pre processing of the pattern in conjunction with suffix match lengths recorded at each match attempt. Storing suffix match lengths requires an additional table equal in size to the text being searched. The Raita algorithm improves the performance of Boyer–Moore–Horspool algorithm. The searching pattern of particular sub string in a given string is different from Boyer–Moore–Horspool algorithm.