Когато попада на термина „търсене на текст“, обикновено се мисли за голям текст, който е индексиран по начин, който дава възможност бързо да се търсят една или повече думи за търсене, когато те са въведени от потребител. Това е класически проблем за компютърни учени , за които съществуват много решения.
Но какво ще кажете за обратен сценарий? Какво ще стане, ако това, което е достъпно за индексиране предварително, е група фрази за търсене и само по време на изпълнение е представен голям текст за търсене? Тези въпроси са това, което този урок за структурата на данните се опитва да отговори.
Приложения
Приложението в реалния свят за този сценарий е съпоставяне на редица медицински тези със списък на медицински състояния и откриване на кои тези обсъждат кои състояния. Друг пример е обхождането на голяма колекция от съдебни прецеденти и извличане на законите, на които се позовават.
Директен подход
Най-основният подход е да преглеждате фразите за търсене и да търсите в текста всяка фраза, една по една. Този подход не се мащабира добре. Търсенето на низ в друг има сложността На) . Повтаряйки това за м фрази за търсене води до ужасното O (m * n) .
(Вероятно само) предимството на директен подход, който е лесен за изпълнение, както е видно от следния фрагмент на C #:
String[] search_phrases = File.ReadAllLines ('terms.txt'); String text_body = File.ReadAllText('body.txt'); int count = 0; foreach (String phrase in search_phrases) if (text_body.IndexOf (phrase) >= 0) ++count; Изпълнявам този код на моята машина за разработка [един] срещу тестова проба [2] , Получих време на работа от 1 час и 14 минути - далеч след времето, което трябва да вземете чаша кафе, да станете и да се разтегнете или каквото и да е друго оправдание, което разработчиците използват, за да пропуснат работата.
превърнете raspberry pi в уеб сървър
По-добър подход - The Trie
Предишният сценарий може да бъде подобрен по няколко начина. Например процесът на търсене може да бъде разделен и паралелизиран на множество процесори / ядра. Но намаляването на времето за изпълнение, постигнато от този подход (общо време на изпълнение от 20 минути, предполагащо перфектно разделяне на 4 процесора / ядра), не оправдава допълнителната сложност на кодирането / отстраняването на грешки.
Най-доброто възможно решение би било това, което преминава през текстовото тяло само веднъж. Това изисква фразите за търсене да бъдат индексирани в структура, която може да се трансформира линейно, успоредно с текстовото тяло, с един проход, постигайки крайна сложност на На) .
Структура на данни, която е особено подходяща точно за този сценарий, е трие . Тази гъвкава структура на данни обикновено се пренебрегва и не е толкова известна, колкото другите свързани с дърветата структури, когато става въпрос за проблеми с търсенето.
Предишният урок на ApeeScape за опити предоставя отлично въведение в това как са структурирани и използвани. Накратко, трие е специално дърво, способно да съхранява последователност от стойности по такъв начин, че проследяването на пътя от корена до който и да е възел дава валидно подмножество на тази последователност.
Така че, ако можем да комбинираме всички фрази за търсене в едно трие, където всеки възел съдържа дума, ще имаме фразите, изложени в структура, където простото проследяване от корена надолу, чрез който и да е път, дава валидна фраза за търсене.
Предимството на трие е, че значително намалява времето за търсене. За да улесним разбирането за целите на този урок за трие, нека си представим двоично дърво. Преминаването по двоично дърво има сложността на O (log2н) , тъй като всеки възел се разклонява на две, намалявайки наполовина останалия ход. Като такова, троичното дърво има сложността на преминаване O (log3н) . В трие обаче броят на дъщерните възли се диктува от последователността, която представлява, а в случай на четим / смислен текст, броят на децата обикновено е голям.
Алгоритъм за търсене на текст
Като прост пример, нека приемем следните фрази за търсене:
- „Едно и също семейство“
- „Различно семейство“
- „Отделно съществуване“
- “Членове на лигата”
Не забравяйте, че знаем нашите фрази за търсене предварително. И така, започваме с изграждането на индекс под формата на трие:
колко github страници мога да имам
По-късно потребителят на нашия софтуер го представя с файл, съдържащ следния текст:
Европейските езици са членове на едно и също семейство. Отделното им съществуване е мит.
Останалото е съвсем просто. Нашият алгоритъм ще има два индикатора (указатели, ако искате), единият започващ в основата или възел „старт“ в нашата структура на трие, а другият на първата дума в тялото на текста. Двата индикатора се движат заедно, дума по дума. Текстовият индикатор просто се придвижва напред, докато индикаторът трие преминава дълбочината на трие, следвайки следа от съвпадащи думи.
Индикаторът за трие се връща, за да започне в два случая: Когато достигне края на клон, което означава, че е намерена фраза за търсене, или когато срещне несъвпадаща дума, в който случай не е намерено съвпадение.
Едно изключение от движението на текстовия индикатор е, когато е намерено частично съвпадение, т.е. след поредица от съвпадения се открива несъвпадение преди края на клона. В този случай текстовият индикатор не се премества напред, тъй като последната дума може да бъде началото на нов клон.
Нека приложим този алгоритъм към нашия пример за структура на данни от trie и да видим как върви:
| Стъпка | Индикатор Trie | Текстов индикатор | Съвпада? | Трие действие | Текстово действие |
|---|---|---|---|---|---|
| 0 | старт | The | - | Преместване в старт | Преминете към следващия |
| един | старт | Европейски | - | Преместване в старт | Преминете към следващия |
| 2 | старт | езици | - | Преместване в старт | Преминете към следващия |
| 3 | старт | са | - | Преместване в старт | Преминете към следващия |
| 4 | старт | членове | членове | Преместване в членове | Преминете към следващия |
| 5 | членове | на | на | Преместване в на | Преминете към следващия |
| 6 | на | на | на | Преместване в на | Преминете към следващия |
| 7 | на | един и същ | - | Преместване в старт | - |
| 8 | старт | един и същ | един и същ | Преместване в един и същ | Преминете към следващия |
| 9 | един и същ | семейство | семейство | Преместване в старт | Преминете към следващия |
| 10 | старт | техен | - | Преместване в старт | Преминете към следващия |
| единадесет | старт | отделно | отделно | Преместване в отделно | Преминете към следващия |
| 12 | отделно | съществуване | съществуване | Преместване в старт | Преминете към следващия |
| 13 | старт | е | - | Преместване в старт | Преминете към следващия |
| 14. | старт | да се | - | Преместване в старт | Преминете към следващия |
| петнадесет | старт | мит | - | Преместване в старт | Преминете към следващия |
Както виждаме, системата успешно намира двете съвпадащи фрази, „Едно и също семейство“ и „Отделно съществуване“ .
какво прави финансовият директор на една компания
Пример от реалния свят
За един неотдавнашен проект бях представен със следния проблем: клиентът има голям брой статии и докторски дисертации, свързани с нейната сфера на работа, и е генерирал свой собствен списък с фрази, представящи конкретни заглавия и правила, отнасящи се до същото поле работа.
Нейната дилема беше следната: предвид списъка й с фрази, как тя свързва статиите / тезите с тези фрази? Крайната цел е да можете да избирате произволно група фрази и веднага да имате списък със статии / тези, в които се споменават тези конкретни фрази, готови за грабване.
Както беше обсъдено по-рано, има две части за решаването на този проблем: Индексиране на фразите в трие и действителното търсене. Следващите раздели предоставят проста реализация в C #. Моля, обърнете внимание, че обработката на файлове, проблеми с кодирането, изчистването на текст и подобни проблеми не се обработват в тези фрагменти, тъй като те са извън обхвата на тази статия.
Индексиране
Операцията за индексиране просто пресича фрази една по една и ги вмъква в трие, по една дума на възел / ниво. Възлите са представени със следния клас:
class Node { int PhraseId = -1; Dictionary Children = new Dictionary(); public Node() { } public Node(int id) { PhraseId = id; } } Всяка фраза е представена от идентификатор, който може да бъде толкова прост, колкото нарастващо число, и предаден на следната функция за индексиране (променливият корен е действителният корен на трие):
void addPhrase(ref Node root, String phrase, int phraseId) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // break phrase into words String[] words = phrase.Split (); // start traversal at root for (int i = 0; i Търсене
Процесът на търсене е директно изпълнение на трие алгоритъма, обсъден в урока по-горе:
void findPhrases(ref Node root, String textBody) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // a list of found ids List foundPhrases = new List(); // break text body into words String[] words = textBody.Split (); // starting traversal at trie root and first // word in text body for (int i = 0; i производителност
Представеният тук код е извлечен от действителния проект и е опростен за целите на този документ. Пускане на този код отново на същата машина [един] и срещу същата проба за изпитване [2] доведе до изпълнение от 2,5 секунди за изграждане на трие и 0,3 секунди за търсене. Толкова за времето за почивка, а?
Вариации
Важно е да се признае, че алгоритъмът, описан в този урок за трие, може да се провали в определени крайни случаи и затова е проектиран с предварително дефинирани думи за търсене, които вече са на ум.
часова ставка срещу калкулатор на заплата
Например, ако началото на една дума за търсене е идентично с част от друга дума за търсене, както в:
- ' споделям и се наслаждавайте с приятели ”
- „Имам два билета споделям с някого'
и тялото на текста съдържа фраза, която кара показалеца на трие да започне по грешен път, като например:
Имам два билета за споделяне и наслада с приятели.
тогава алгоритъмът няма да успее да съвпадне с който и да е член, тъй като индикаторът за триене няма да се върне към началния възел, докато текстовият индикатор вече не е преминал началото на съответстващия термин в тялото на текста.
Важно е да прецените дали този вид крайни случаи е възможен за вашето приложение, преди да приложите алгоритъма. Ако е така, алгоритъмът може да бъде модифициран с допълнителни трие индикатори за проследяване на всички мачове по всяко време, вместо само едно мачче в даден момент.
Заключение
Търсене на текст е дълбоко поле в компютърните науки; поле, богато на проблеми и решения. Видът данни, с които трябваше да се справя (23MB текст е много книги в реалния живот), може да изглежда като рядко явление или специализиран проблем, но разработчиците, които работят с лингвистични изследвания, архивиране или друг вид манипулация на данни , попадате редовно на много по-големи количества данни.
Както е видно от учебния урок за структурата на данните по-горе, от голямо значение е внимателният избор на правилния алгоритъм за разглеждания проблем. В този конкретен случай подходът на трие намалява времето за изпълнение с изумителните 99,93% от над час на по-малко от 3 секунди.
какво е фонд за търсене
В никакъв случай това не е единственият ефективен подход, но той е достатъчно прост и работи. Надявам се, че този алгоритъм ви е бил интересен и ви пожелавам успех във вашите начинания за кодиране.
[един] Машината, използвана за този тест, има следните характеристики:
- Intel i7 4700HQ
- 16GB RAM
Тестването беше направено на Windows 8.1 с помощта на .NET 4.5.1, а също и на Kubuntu 14.04 с помощта на най-новата версия на mono и резултатите бяха много сходни.
[2] Тестовата проба се състои от 280 000 фрази за търсене с общ размер 23,5 MB и текстово тяло от 1,5 MB.
