Мисля, че започнах да разбирам какво имаш предвид!

Запечатването е проста работа; въвеждане в заявката за търсене и двойно повече. Прочетете всички големи уеб търсачки днес са в състояние да коригират грешки в ключовите думи в 1-ва и да предлагат заявки във 2-ра; след тях същите искат да търсят по-малки. И двете неща могат да бъдат изпълнени хитро с помощта на търсачка с отворен код, наречена Sphinx; В тази публикация ще ви кажа точно как.

Е, за имахте предвид („какво имахте предвид“) и друго завършване на заявка („търсите ли Вася“).

Нека започнем просто, тези. завършване на заявка. Потребителят започва да въвежда ред за търсене, докато въвежда, той иска незабавно да покаже подсказки (това е така, че да не търси неизвестно нещо, но да слуша „Ботуши“, като всички останали). Може би дори с броя на резултатите. Как да направя, откъде да взема данните?

Има около две опции: можете директно да предложите потребителски заявки или можете да използвате отделни ключови думи.

Ключовите думи са особено лесни за предлагане. Програмата за индексиране с неочаквано име indexer има два не по-малко внезапни ключа:--buildstops, който принуждава indexer да изгради списък от N най-често срещани думи (известен още като речник) вместо обикновено индексиране, и--buildfreqsкъм него, който също принуждава честотите да се броят едновременно (известен още като честотен речник). Взимаме индексатор, създаваме 10 хиляди (може би 100) от най-често срещаните думи в нашата колекция от документи:

Получаваме нещо като този файл:

Следващият е въпрос на технология. Създаваме SQL таблица, пишем скрипт за импортиране на дузина редове, използваме обичайния LIKE за подсказка, сортираме резултатите по честота на думата. LIKE на индекса ще се окаже доста бърз, може би. търси началото на ключа. За еднобуквени заявки би било хубаво незабавно да се изчислят предварително и да се кешират резултатите, така чеа не да ринеш с лопата хиляди редове за всяко кихане. Кешът на заявките на MySQL обаче на теория ще запази, ако е активиран.

Заявките се подканват почти по същия начин. Нито знакът, нито LIKE отиват никъде; само вместо отделни думи сега искам цели редове. Можете и трябва да ги вземете в дневника на заявките си и да изчислите честотите от там. Дневникът ще трябва да бъде обработен малко с файл: редът „vasya pupkin“ от гледна точка на търсенето съвпада с „Vasya! Pupkin! ”, Ето защо не е много comme il faut да ги разглеждаме като различни искания. Това се обработва от метода Sphinx API BuildKeywords(): вземаме произволен низ на заявка, изграждаме ключови думи върху него (с преобразуване на главни и малки букви и всичко това), възстановяваме нормализирания низ на заявка. По-добре е да направите всичко това, като първо установите постоянна връзка с помощта на метода Open(), в противен случай ще работи многократно по-бавно. Е, и тогава вече на набраздения; журнал, файл, сортиране, uniq -c, импортиране на скрипт, SQL таблица, ХАРЕСВАНЕ, печалба. Файлът трябва да изглежда така:

Оставяме скрипта за импортиране от текстов файл за две полета в SQL базата данни като домашна работа за читателите.

Разбирам, че това е намек.

Разбира се, винаги има опция да завинтите ispell, aspell, hunspell или който и да е модерен днес заклинание. Ясно е, че винаги зависи или от качеството на xxxspell-речника, или глупаво в отсъствието му за желания език. Ясно е, че не помага при неологизми (preved), специални термини (acidium acetylosalicilium), географски имена и т.н. Все още те кара да искаш повече. И блогът не е за ispell, трябва да се съобразите.

Отново е необходим честотен речник. Вярно, по-големи от 10K ключови думи - не си струва да „коригирате“ рядка правилна дума в близка често срещана дума. Речник за 1 милион думи обикновено трябва да е достатъчен, за 10 милиона трябва да е,тези. командата става indexer --buildstops dict.txt 10000000 --buildfreqs MYINDEXNAME (работи с над 20 MB/сек на C2D E8500 btw). За разлика от подсказките, SQL търсенето в такъв речник няма да помогне по никакъв начин; и има повече данни, и типът на заявките е напълно различен. Но Сфинкс ще помогне.

Основната идея е следната. Ние генерираме за всяка дума от речниканабор от триграми, тези. 3 последователни знака. Ние индексираме триграмите със Сфинкс. За да търсим опции за заместване, ние изграждаме триграми и за грешно изписаната дума, потърсете ги в индекса. Кандидатите са няколко. Колкото повече триграми съвпадат, толкова по-малко се различава дължината на думата и колкото по-разпространена е намерената опция, толкова по-добре. И сега ще анализираме всичко това по-подробно, използвайки жив пример.

Речникът, създаден от indexer --buildstops, все още изглежда така (избрах различна част, така че думите да са по-автентични и примерът да е по-ясен):

За всяка дума трябва да създадем уникален идентификатор, да запазим самата дума и нейната честота, да изградим триграми и да запазим всичко това в базата данни. Ако има правописни грешки в индексираната база данни, има смисъл да отхвърлите думи, които са твърде редки, може би. Има голяма вероятност това да са правописни грешки.

Само полето с триграми трябва да бъде индексирано, но за класиране на кандидатите (т.е. избор на най-добрата корекция) ще се изисква и дължината на думата и честотата на нейното появяване в колекцията.

Идентифицираме подозрителни думи от резултатите от заявката за търсене: ако има твърде малко резултати от търсенето (или никакви), анализираме раздела за отговор $result["words"], разглеждаме броя на документите за всяка дума. Ако има малко документи, ние се опитваме да коригираме такава дума. Например, за заявката „зелена светлина“ в моя тестов индекс, броят на срещанията за „зелена“ е 34421, за „светла“ само 2. Кое от тях да поставитепоправителна работа, ясно веднага. Конкретните прагове за "малко" са много индивидуални за различните колекции от документи и запитвания. Погледнете в речника си и дневника на заявките, изберете магически константи.

Изграждаме триграми, изпълняваме заявка по специалния индекс на триграми. Тъй като думата е изписана неправилно,всичкитриграми е малко вероятно да съвпаднат. От друга страна, ако съвпада само една триграма, такъв кандидат също не представлява голям интерес: това може да се случи само ако съвпадат три букви в средата на думата (и нищо друго) или една буква в началото (и нищо друго). Е, ние използваме оператора за кворум, той изглежда точно така: издава всички документи, където съвпадат поне 2 триграми. Въвеждаме и ограничение на дължината: приемаме, че дължината на правилния вариант се различава с не повече от 2 знака.

Куп намерени кандидати трябва да бъдат сортирани и най-добрият избран от тях. Припомняме си какви фактори имаме:

1. колкото повече триграми съвпадат, толкова по-добре;
2. колкото по-малка е разликата в дължината на думата, толкова по-добре;
3. колкото по-разпространен е намереният вариант, толкова по-добре.

Всички тези фактори най-новата версия на Sphinx може да изчисли и сортира напълно от страната на сървъра. Броят на съвпадащите триграми може да се изчисли с помощта на ранкера SPH_RANK_WORDCOUNT (тъй като по време на нашето специално търсене всяка триграма действа като отделна ключова дума). Разликата в дължината на думата е abs(len-$len) и честотата се съхранява в атрибута freq. Изчисляваме факторите, събираме някои и избираме най-добрия:

Ура, работи! За думата светлина коригиращата светлина е успешно намерена. (По-точно, Sphinx намира ID, който след това получава низа „light“ от базата данни).

Ето как е подредена демонстрацията, прикачена към Sphinx 0.9.9-rc2 (вижте директорията misc/suggest в архива),което можете незабавно да тествате върху вашите данни, без да пишете допълнителен код :-)

Демото, веднага става ясно, не е идеално и подлежи на фина настройка с файл. (Съжалявам, не се сдържах.) Има опасност извън кутията PHP частта да не работи с български език, защото се очаква UTF-8, използва се substr и съответно без mbstring.overload=7 никъде. Почти сигурно ще трябва да завъртите FREQ_THRESHOLD, тези. минималният брой срещания, под който думата се счита за печатна грешка и не попада в специалния индекс; понижаване за малки колекции от данни, повишаване на мащаба за големи. По същите причини (за да не се класира редкият боклук над често срещания небоклук), може да се наложи да се изкриви формулата за изчисляване на myrank. Например, добавете допълнителна единица към броя на съвпадащите триграми за честоти, които се различават 1000 пъти:

Освен това трикът с триграмата е мощен, но много прост и оставя много извън уравнението. Редът на триграмите не се взема предвид, въпреки че за думи с разумна дължина това обикновено не е проблем. По-интересното е, чене се взема предвид, тъй катохората грешат: пермутацията на 2 съседни букви според броя на триграмите е неразличима от замяната на тези букви свсякакви(!) Други (например светлина/lihgt/limit); близостта на буквите на клавиатурата не се взема предвид по никакъв начин; фонетичната близост (всъщност/akshully) не се взема предвид по никакъв начин. Доста очевидна идея за подобряване на качеството на корекциите с малко кръвопролитие: вместо 1 най-добър вариант, ние изваждаме 10-20 парчета, изчисляваме разстоянието на Левенщайн на клиента и коригираме резултатите от изчислението. С много кръв можете да „преброите“ дузина или двама кандидати по същия начин с всеки друг алгоритъм, написан от вас.

Като цяло, демото ще работи от кутията. Но това все още е демонстрация и никой не е отменил много пространство за по-нататъшно творчество. създавам,измисляйте, пишете блогове, изпращайте кръпки!

---