размита търсене
С Throk дължина х | х | = М се изписва като x1 x2. х. където XI представлява I ия символ х.
Подниз XI XI + 1. XJ линия х, където<=j<=m. будет обозначаться x(i,j). В случае, когда i>й, обърната подниз означен XR (I, J).
Обикновено х ще покаже желаната пробата и у - текстов низ; | X | = М, | у | = N, и, разбира се, т<=n.
х = Трисмегист
| X | = 12
х (7,10) = Основно съдържание
XR (7,4) = камъни
Обобщените задачи съвпадение линии включва намирането на поднизове на текста в близост до дадена текстура линия, наричана още неясни струни съвпадение задача. Fuzzy низ съвпадение проблем може да бъде формулиран, както следва:
Нека там да се даде проба х, | х | = M и текст у, | г | = N, m, п> 0 и m Hamming Разстояние [Hamming 1982] между две линии на същата дължина се определя като броя на позициите в които символите не съвпадат. Това е еквивалентно на минималната ниско превръщане на първия ред на втория, когато процесът на смяна е разрешено само до единично тегло. Ако позволи сравнение на низове с различна дължина, обикновено също се изисква поставяне и премахване. Ако му се даде същата тежест като замяната на минималната обща конверсионна цена ще бъде равна на една от предложените от Левенщайн [Левънстийн, 1965] показатели. Друг показател, равна на минималната цена преобразуване в случаите, когато е разрешено само вмъкването и изтриването. Това е еквивалентно на отстраняване 1 ценообразуване и поставяне, и замествайки 2, като последният може да бъде заменен от двойка вмъкване-заличаване. Първият от тези показатели, ние се позоваваме долу Левънстийн разстояние. а вторият - редактиране разстояние. По този начин проблемът се крие във факта, че за дадена функция на разстояние, за да намерите всички срещания на текст, които се отделят от пробата с не повече от к. Ако г е разстоянието на Хеминг, задачата се нарича чрез сравняване на низове с к несъответствия. ако г - Левенщайн разстояние, задачата се нарича чрез сравняване на низове с к разлики (или понякога грешки). Най-наивен подход към проблема на съвпадение линии, които изискват време O (Минесота), лесно се адаптират към несъответствията задачата к, което позволява на к несъответствия при сравнения подниз на знаци в текста. Въпреки това, както за проблема на съвпадение редове за задачи, к к несъответствия и различия са били измислени по-ефективни подходи. Тяхната алгоритъм е много по-добре, ако част к о (т / дневник п). За несвързани азбуки това алгоритъм бързо, ако к пропорционална О (влизане 1/2 т). Това със сигурност е отлично, когато границата к е О (влезте 1/2 м). Имайте предвид обаче, че за голяма к, това е, когато к е равно на O (m), изпълнението му не е по-добре от пряк адаптация, с квадратно време, динамичен подход за програмиране. От практическа гледна точка, особено препоръчвам Ако целта на размита търсене - за да се изключи грешка словослагател, методът е оптимизиран за търсене е много подобен на модела на събития, описани в статията Също така, аз ви съветваме да посетите ITMAN сайт. той е посветен изключително на размита търсене и, по мое мнение, е доста интересно.
aGREP цип
Опитва за приблизителното низ съвпадение цип