Кіріспе
Үлгіге шамамен сәйкес келетін тізбектерді табу
Компьютерлік ғылымда шамамен сәйкес келетін тізбектерді табу (көбінесе «бұлыңғыр тізбек іздеу» деп аталады) – бұл үлгіге нақты сәйкес келмей, шамамен сәйкес келетін тізбектерді табу әдісі. Шамамен тізбек сәйкестігі мәселесі әдетте екі кіші мәселеге бөлінеді: берілген тізбек ішінде шамамен сәйкес келетін тізбектерді табу және үлгіге шамамен сәйкес келетін сөздік тізбектерін табу.
Онлайн және офлайн
Дәстүрлі түрде, шамамен тізбектерді сәйкестендіру алгоритмдері екі санатқа бөлінеді: желілік және желіден тыс. Желілік алгоритмдерде үлгіні іздеу алдында өңдеуге болады, бірақ мәтінді өңдеуге болмайды. Басқаша айтқанда, желілік техникалар индекссіз іздеуді жүзеге асырады. Желілік шамамен сәйкестікті іздеудің алғашқы алгоритмдерін Вагнер мен Фишер және Селлерс ұсынған. Екі алгоритм де динамикалық бағдарламалауға негізделген, бірақ әртүрлі мәселелерді шешеді. Селлерс алгоритмі мәтіндегі кіші тізбекті шамамен іздейді, ал Вагнер мен Фишер алгоритмі Левенштейн қашықтығын есептейді, ол тек сөздіктегі шамамен іздеуге ғана қолайлы. Желілік іздеу техникалары бірнеше рет жетілдірілді. Ең танымал жақсартулардың бірі – битап алгоритмі (сонымен қатар «ауыстыру және» немесе «ауыстыру және есептеу» алгоритмі деп те аталады), ол салыстырмалы түрде қысқа үлгілер үшін өте тиімді. Битап алгоритмі Unix іздеу құралының agrep негізі болып табылады. Желілік іздеу алгоритмдеріне G. Navarro шолу жасаған. Жедел желілік техникалар бар болғанымен, олардың үлкен деректердегі өнімділігі қанағаттандырмайды. Мәтінді алдын ала өңдеу немесе индекстеу іздеуді едәуір жылдамдатады. Бүгінде әртүрлі индекстеу алгоритмдері ұсынылған. Олардың арасында жұрнақ ағаштары, метрикалық ағаштар және n-грамма әдістері бар. Наварро және авторлар тобы мәтінде кез келген кіші тізбекті табуға мүмкіндік беретін индекстеу техникаларын егжей-тегжейлі қарастырады. Бойцов сөздік әдістерінің (яғни, іздеу үлгісіне шамамен сәйкес келетін барлық сөздік сөздерін табуға мүмкіндік беретін әдістер) есептеулік шолуын ұсынады.
famous improvement is the bitap algorithm (also known as the shift or and shift and algorithm), which is very efficient for relatively short pattern strings. The Bitap algorithm is the heart of the Unix searching utility agrep. A review of on line searching algorithms was done by G. Navarro. Although very fast on line techniques exist, their performance on large data is unacceptable. Text preprocessing or indexing makes searching dramatically faster. Today, a variety of indexing algorithms have been presented. Among them are suffix trees, metric trees and n gram methods. A detailed survey of indexing techniques that allows one to find an arbitrary substring in a text is given by Navarro et al. A computational survey of dictionary methods (i. e., methods that permit finding all dictionary words that approximately match a search pattern) is given by Boytsov.
Қолданбалар
Тақалған сәйкестіктің кең таралған қолданыстарының бірі - әріптік қателерді тексеру. ДНК деректерінің көп көлемі пайда болғаннан бері, нуклеотидтік тізбектерді сәйкестендіру маңызды қолданысқа айналды. Шамамен сәйкестікті спам-сүзгілеуде де қолданады. Мәліметтерді байланыстыру - екі әртүрлі дерекқордан алынған мәліметтерді сәйкестендірудің кең таралған тәсілі. Көптеген екілік деректерге, мысалы, суреттер мен музыкаға, тізбекті сәйкестендіру алгоритмдерін қолдануға болмайды. Оларға басқа алгоритмдер қажет, мысалы, дыбыстық ізтаңбаны анықтау. fzf деп аталатын кең таралған командалық қабық құралы әртүрлі командалық қабық қолданбаларына шамамен тізбектік іздеуді енгізу үшін жиі қолданылады.