Кіріспе
Шамамен тізбекті сәйкестендіру алгоритмі
Битап алгоритмі (сонымен қатар, жылжыту немесе, жылжыту және немесе Баэза-Ятс-Гоннет алгоритмі деп те аталады) – шамамен тізбекті сәйкестендіру алгоритмі. Алгоритм берілген мәтінде берілген үлгіге «шамамен тең» болатын кіші тізбек бар-жоқ екенін анықтайды, мұнда шамамен теңдік Левенштейн қашықтығы тұрғысынан анықталады. Егер кіші тізбек пен үлгінің арасындағы қашықтық берілген k мәніне тең немесе одан кем болса, алгоритм оларды тең деп есептейді. Алгоритм үлгінің әр элементі үшін бір биттен тұратын биттік маскалар жиынтығын алдын ала есептеуден басталады. Содан кейін ол көп бөлігінде біттік операцияларды қолдана алады, олар өте жылдам. Битап алгоритмі, әсіресе, Юникс құралының agrep негізгі алгоритмі ретінде танымал, оны Уди Манбер, Сун Ву және Бура Гопал жасаған. Манбер мен Вудың бастапқы мақаласы алгоритмді жалпы реттегіш өрнектердің шамалы сәйкестігін қамтамасыз ету үшін кеңейтулерді ұсынады. Алгоритмге қажетті дерек құрылымдарының есебінен, ол тұрақты ұзындығынан кем үлгілерде (әдетте, машинаның сөз ұзындығы) жақсы жұмыс істейді, сондай-ақ кішкентай әліпбидегі кірістерді артық көреді. Дегенмен, белгілі бір әліпби және сөз ұзындығы m үшін іске асырылғаннан кейін, оның орындалу уақыты толығымен болжамды – ол мәтіннің немесе үлгінің құрылысына қарамастан O(mn) операциясында жұмыс істейді. Дәл тізбекті іздеуге арналған битап алгоритмін 1964 жылы Балинт Дёмелки ойлап тапты және 1977 жылы Р.К. Шьямасундар кеңейтті, ал 1989 жылы Рикардо Баэза-Ятс және Гастон Гоннет қайта ойлап тапты (бірінші автордың докторлық диссертациясының бір бөлімі), сонымен қатар оны таңбалар кластарын, жоққа шығару белгілерін және сәйкессіздіктерді өңдеуге дейін кеңейтті. 1991 жылы Манбер мен Ву оны енгізулер мен жоюларды (толық шамалы тізбекті іздеу) өңдеу үшін кеңейтті. Бұл алгоритмді кейін 1996 жылы Баэза-Ятс және Наварро жетілдірді. Мазмұны
The bitap algorithm (also known as the shift or, shift and or Baeza Yates Gonnet algorithm) is an approximate string matching algorithm. The algorithm tells whether a given text contains a substring which is "approximately equal" to a given pattern, where approximate equality is defined in terms of Levenshtein distance if the substring and pattern are within a given distance k of each other, then the algorithm considers them equal. The algorithm begins by precomputing a set of bitmasks containing one bit for each element of the pattern. Then it is able to do most of the work with bitwise operations, which are extremely fast. The bitap algorithm is perhaps best known as one of the underlying algorithms of the Unix utility agrep, written by Udi Manber, Sun Wu, and Burra Gopal. Manber and Wu's original paper gives extensions of the algorithm to deal with fuzzy matching of general regular expressions. Due to the data structures required by the algorithm, it performs best on patterns less than a constant length (typically the word length of the machine in question), and also prefers inputs over a small alphabet. Once it has been implemented for a given alphabet and word length m, however, its running time is completely predictableit runs in O(mn) operations, no matter the structure of the text or the pattern. The bitap algorithm for exact string searching was invented by Bálint Dömölki in 1964 and extended by R. K. Shyamasundar in 1977, before being reinvented by Ricardo Baeza Yates and Gaston Gonnet in 1989 (one chapter of first author's PhD thesis) which also extended it to handle classes of characters, wildcards, and mismatches. In 1991, it was extended by Manber and Wu to handle also insertions and deletions (full fuzzy string searching). This algorithm was later improved by Baeza Yates and Navarro in 1996. TOC
Сыртқы сілтемелер мен сілтемелер
Балинт Дёмёлки, Синтаксистік талдау алгоритмі, Есептеу лингвистикасы 3, Венгрия ғылым академиясы, 29–46 б., 1964 ж. Балинт Дёмёлки, Өндіріс ережелеріне негізделген әмбебап компилятор жүйесі, BIT Numerical Mathematics, 8(4), 262–275 б., 1968 ж. Р. К. Шьямасундар, Дёмёлки алгоритмін қолдана отырып, прецеденттік талдау, Компьютерлік математика халықаралық журналы, 6(2), 105–114 б., 1977 ж. Рикардо Баэза Йейтс. "Мәтінді тиімді іздеу". PhD диссертациясы, Ватерлоо университеті, Канада, 1989 жылғы мамыр. Уди Манбер, Сун Ву. "Текст қателері бар жылдам іздеу". Техникалық есеп TR 91 11. Компьютерлік ғылымдар кафедрасы, Аризона университеті, Тусон, 1991 жылғы маусым. (PostScript zipped) Рикардо Баэза Йейтс, Гастон Х. Гоннет. "Мәтін іздеудің жаңа тәсілі". ACM хабарламалары, 35(10), 74–82 б., 1992 жылғы қазан. Уди Манбер, Сун Ву. "Тексттік іздеу қателерге жол береді". ACM хабарламалары, 35(10), 83–91 б., 1992 жылғы қазан. Р. Баэза Йейтс және Г. Наварро. Шамамен сәйкес келетін тізбекті жылдам табу алгоритмі. Дэн Хирксберг және Джин Майерс (ред.), Комбинациялық үлгілерді сәйкестендіру (CPM'96), LNCS 1075, 1–23 б., Ирвин, Калифорния, 1996 жылғы маусым. Г. Майерс. "Динамикалық бағдарламалауға негізделген, шамамен сәйкес келетін тізбектерді табу үшін жылдам биттік векторлық алгоритм". ACM журналы 46(3), 1999 жылғы мамыр, 395–415 б. libbitap – алгоритмнің көптеген тұрақты өрнектерге оңай кеңейтілуін көрсететін тегін іске асыру. Жоғарыдағы кодтан айырмашылығы, бұл үлгі ұзындығына шектеу қоймайды. Рикардо Баэза Йейтс, Бертье Рибейро Нето. Қазіргі заманғы ақпаратты іздеу. 1999 ж. bitap.py – Ву Манбердің модификацияларымен Bitap алгоритмін Python тілінде іске асыру.
Ricardo Baeza Yates, Gastón H. Gonnet. "A New Approach to Text Searching." Communications of the ACM, 35(10): pp. 74–82, October 1992. Udi Manber, Sun Wu. "Fast text search allowing errors." Communications of the ACM, 35(10): pp. 83–91, October 1992, R. Baeza Yates and G. Navarro. A faster algorithm for approximate string matching. In Dan Hirchsberg and Gene Myers, editors, Combinatorial Pattern Matching (CPM'96), LNCS 1075, pages 1–23, Irvine, CA, June 1996. G. Myers. "A fast bit vector algorithm for approximate string matching based on dynamic programming." Journal of the ACM 46 (3), May 1999, 395–415. libbitap, a free implementation that shows how the algorithm can easily be extended for most regular expressions. Unlike the code above, it places no limit on the pattern length. Ricardo Baeza Yates, Berthier Ribeiro Neto. Modern Information Retrieval. 1999. bitap. py Python implementation of Bitap algorithm with Wu Manber modifications.