Иголка в стоге сена: отличный учебник по крупномасштабному текстовому поиску

При столкновении с термином «текстовый поиск» обычно думают о большом массиве текста, который проиндексирован таким образом, что позволяет быстро найти одно или несколько условий поиска, когда они вводятся пользователем. Это классическая проблема компьютерных ученых, для которой существует множество решений.

Но как насчет обратного сценария? Что, если заранее для индексации доступна группа поисковых фраз, и только во время выполнения для поиска предоставляется большой объем текста? На эти вопросы и направлено это руководство по структуре данных trie.

Приложения

Реальное применение этого сценария заключается в сопоставлении ряда медицинских тезисов со списком медицинских состояний и выяснении, какие тезисы обсуждают какие состояния. Другой пример — просмотр большой коллекции судебных прецедентов и извлечение законов, на которые они ссылаются.

Прямой подход

Самый простой подход состоит в том, чтобы перебирать поисковые фразы и искать в тексте каждую фразу одну за другой. Этот подход плохо масштабируется. Поиск строки внутри другой имеет сложность O(n) . Повторение этого для m поисковых фраз приводит к ужасному 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;

Запустив этот код на моей машине для разработки [1] на тестовом образце [2], я получил время выполнения 1 час 14 минут — намного больше времени, которое вам нужно, чтобы выпить чашку кофе, встать и потянуться или по любому другому оправданию. разработчики используют, чтобы пропустить работу.

Лучший подход — попытка

Предыдущий сценарий можно улучшить несколькими способами. Например, процесс поиска можно разделить и распараллелить на нескольких процессорах/ядрах. Но сокращение времени выполнения, достигнутое при таком подходе (общее время выполнения 20 минут при идеальном разделении на 4 процессора/ядра), не оправдывает дополнительную сложность кодирования/отладки.

Наилучшим возможным решением будет тот, который проходит через тело текста только один раз. Это требует, чтобы поисковые фразы были проиндексированы в структуру, которая может быть пройдена линейно, параллельно с телом текста, за один проход, достигая конечной сложности O(n) .

Структура данных, которая особенно хорошо подходит именно для этого сценария, — это trie . Эта универсальная структура данных обычно упускается из виду и не так известна, как другие древовидные структуры, когда дело доходит до задач поиска.

Предыдущее руководство Toptal по попыткам дает отличное представление о том, как они структурированы и используются. Короче говоря, дерево — это специальное дерево, способное хранить последовательность значений таким образом, что отслеживание пути от корня до любого узла дает допустимое подмножество этой последовательности.

Итак, если мы сможем объединить все поисковые фразы в одно дерево, где каждый узел содержит слово, у нас будут фразы, расположенные в структуре, в которой простое прослеживание от корня вниз по любому пути дает действительную поисковую фразу.

Преимущество trie в том, что он значительно сокращает время поиска. Чтобы упростить понимание этого руководства по трем, давайте представим бинарное дерево. Обход бинарного дерева имеет сложность O(log 2 n) , поскольку каждый узел разветвляется на два, сокращая оставшийся обход вдвое. Таким образом, тройное дерево имеет сложность обхода O(log 3 n) . Однако в дереве число дочерних узлов определяется последовательностью, которую оно представляет, а в случае читаемого/осмысленного текста количество дочерних узлов обычно велико.

Алгоритм текстового поиска

В качестве простого примера возьмем следующие поисковые фразы:

• «та же семья»
• «другая семья»
• «отдельное существование»
• «члены лиги»

Помните, что мы заранее знаем наши поисковые фразы. Итак, мы начинаем с построения индекса в виде дерева:

Позже пользователь нашего программного обеспечения представляет ему файл, содержащий следующий текст:

Европейские языки являются членами одной семьи. Их отдельное существование — миф.

Остальное довольно просто. В нашем алгоритме будет два индикатора (указателя, если хотите), один начинается с корня или «начального» узла в нашей структуре trie, а другой — с первого слова в теле текста. Два индикатора движутся вместе, слово за словом. Индикатор текста просто перемещается вперед, в то время как индикатор trie перемещается по дереву в глубину, следуя по следу совпадающих слов.

Индикатор trie возвращается к началу в двух случаях: когда он достигает конца ветви, что означает, что искомая фраза была найдена, или когда он встречает несоответствующее слово, и в этом случае совпадение не найдено.

Единственным исключением из перемещения текстового индикатора является обнаружение частичного совпадения, т. е. после серии совпадений обнаруживается несовпадение до окончания ветви. В этом случае текстовый индикатор не перемещается вперед, так как последнее слово может быть началом новой ветви.

Давайте применим этот алгоритм к нашему примеру структуры данных trie и посмотрим, как это работает:

Как мы видим, система успешно находит две совпадающие фразы: «одна и та же семья» и «отдельное существование» .

Пример из реального мира

Для недавнего проекта я столкнулся со следующей проблемой: клиент имеет большое количество статей и докторских диссертаций, относящихся к области ее работы, и создал свой собственный список фраз, представляющих определенные заголовки и правила, относящиеся к одной и той же области деятельности. работай.

Ее дилемма заключалась в следующем: учитывая ее список фраз, как она связывает статьи/тезисы с этими фразами? Конечная цель состоит в том, чтобы иметь возможность случайным образом выбрать группу фраз и сразу же получить готовый к захвату список статей/тезисов, в которых упоминаются эти конкретные фразы.

Как обсуждалось ранее, решение этой проблемы состоит из двух частей: индексация фраз в дереве и фактический поиск. В следующих разделах представлена ​​простая реализация на C#. Обратите внимание, что обработка файлов, проблемы с кодировкой, очистка текста и подобные проблемы не рассматриваются в этих фрагментах кода, поскольку они выходят за рамки этой статьи.

Индексация

Операция индексирования просто просматривает фразы одну за другой и вставляет их в дерево, по одному слову на узел/уровень. Узлы представлены следующим классом:

 class Node { int PhraseId = -1; Dictionary<String, Node> Children = new Dictionary<String, Node>(); public Node() { } public Node(int id) { PhraseId = id; } }

Каждая фраза представлена ​​идентификатором, который может быть таким же простым, как возрастающее число, и передается следующей функции индексации (переменная root — это фактический корень дерева):

 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 < words.Length; ++i) { // if the current word does not exist as a child // to current node, add it if (node.Children.ContainsKey(words[i]) == false) node.Children.Add(words[i], new Node()); // move traversal pointer to current word node = node.Children[words[i]]; // if current word is the last one, mark it with // phrase Id if (i == words.Length - 1) node.PhraseId = phraseId; } }

Searching

Процесс поиска является прямой реализацией алгоритма trie, описанного в руководстве выше:

 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<int> foundPhrases = new List<int>(); // 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 < words.Length;) { // if current node has current word as a child // move both node and words pointer forward if (node.Children.ContainsKey(words[i])) { // move trie pointer forward node = node.Children[words[i]]; // move words pointer forward ++i; } else { // current node does not have current // word in its children // if there is a phrase Id, then the previous // sequence of words matched a phrase, add Id to // found list if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); if (node == root) { // if trie pointer is already at root, increment // words pointer ++i; } else { // if not, leave words pointer at current word // and return trie pointer to root node = root; } } } // one case remains, word pointer as reached the end // and the loop is over but the trie pointer is pointing to // a phrase Id if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); }

Представление

Представленный здесь код взят из реального проекта и упрощен для целей данного документа. Повторный запуск этого кода на той же машине [1] и с тем же тестовым образцом [2] привел к тому, что время выполнения составило 2,5 секунды для построения дерева и 0,3 секунды для поиска. Так много для перерыва, а?

Вариации

Важно признать, что алгоритм, описанный в этом руководстве по дереву, может дать сбой в определенных пограничных случаях, и поэтому он разработан с учетом предопределенных условий поиска.

Например, если начало одного поискового запроса совпадает с частью другого поискового запроса, например:

• « поделиться и наслаждаться с друзьями»
• «У меня есть два билета , чтобы поделиться с кем-то»

а тело текста содержит фразу, из-за которой указатель trie начинает двигаться по неверному пути, например:

У меня есть два билета, которыми я могу поделиться с друзьями.

тогда алгоритму не удастся сопоставить ни один термин, потому что индикатор trie не вернется к начальному узлу до тех пор, пока индикатор текста не пройдет начало соответствующего термина в теле текста.

Перед реализацией алгоритма важно рассмотреть, возможен ли такой пограничный случай для вашего приложения. Если это так, алгоритм можно модифицировать с помощью дополнительных индикаторов триады, чтобы отслеживать все совпадения в любой момент времени, а не только одно совпадение за раз.

Заключение

Текстовый поиск — это глубокая область компьютерных наук; область, богатая как проблемами, так и решениями. Тип данных, с которыми мне приходилось иметь дело (23 МБ текста — это тонна книг в реальной жизни), может показаться редким явлением или специализированной проблемой, но разработчики, которые занимаются лингвистическими исследованиями, архивированием или любым другим типом обработки данных , регулярно сталкиваться с гораздо большими объемами данных.

Как видно из приведенного выше руководства по структуре данных trie, очень важно тщательно выбрать правильный алгоритм для решения поставленной задачи. В этом конкретном случае подход trie сократил время выполнения на ошеломляющие 99,93%, с более чем часа до менее чем 3 секунд.

Это ни в коем случае не единственный эффективный подход, но он достаточно прост и работает. Я надеюсь, что вы нашли этот алгоритм интересным, и желаю вам удачи в ваших усилиях по программированию.

[1] Машина, использованная для этого теста, имеет следующие характеристики:

• Intel i7 4700HQ
• 16 ГБ ОЗУ

Тестирование проводилось на Windows 8.1 с использованием .NET 4.5.1, а также на Kubuntu 14.04 с использованием последней версии mono, и результаты были очень похожими.

[2] Тестовая выборка состоит из 280 тыс. поисковых фраз общим размером 23,5 МБ и текстовым телом 1,5 МБ.