Статьи

Введение в индексирование и поиск

Сентябрь 2, 2017

Эта статья была первоначально опубликована как « Индексирование и поиск (C #) » 15 июня 2013 года на ранчо программистов. Это было немного обновлено здесь. Исходный код доступен в репозитории Gigi Labs Bitbucket .

Эта статья посвящена индексированию и поиску: что позволяет искать тысячи документов менее чем за секунду?

Чтобы понять, как работает индексирование, мы будем использовать пример, где у нас есть следующие три документа:

doc1.txt contains:
The Three Little Pigs

doc2.txt contains:
The Little Red Riding Hood

doc3.txt contains:
Beauty And The Beast

Теперь предположим, что вы хотите выяснить, какие из этих документов содержат определенное слово, например, «Маленький». Самый простой способ сделать это — просмотреть каждое слово в каждом документе, один за другим, и посмотреть, есть ли в этом документе слово «Little». Концептуально, мы говорим об этом:

indexingsearch-donkeyway

Сделать это в C # очень просто:

string[] documents = { "doc1.txt", "doc2.txt", "doc3.txt" };
string keyword = Console.ReadLine();

foreach (string document in documents)
{
if (File.ReadAllText(document).Contains(keyword))
{
    Console.WriteLine(document);
}
}
Console.ReadKey(true);

Не забудьте поставить в  using System.IO;верхней части, чтобы иметь возможность использовать File. Если вы нажмете F5 и протестируете эту программу, вы увидите, что она работает:

indexingsearch-donkeyout

Однако этот метод не годится, потому что он займет больше времени, поскольку документы становятся больше (больше слов) и более многочисленными (больше документов).

Правильный способ быстрой обработки поисковых запросов — это создание индекса. Это будет выглядеть примерно так:

indexingsearch индекс

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

Мы можем сделать это в C #, сначала создав индекс (не забудьте добавить  using System.Collections.Generic;вверху):

// Build the index
string[] documents = { "doc1.txt", "doc2.txt", "doc3.txt" };
Dictionary<string, List<string>> index = new Dictionary<string, List<string>>();

foreach (string document in documents)
{
string documentStr = File.ReadAllText(document);
string[] words = documentStr.Split();

foreach (string word in words)
{
if (!index.ContainsKey(word))
index[word] = new List<string>();

index[word].Add(document);
}
}

… А затем с помощью индекса быстро и эффективно искать документы:

// Query the index
string keyword = Console.ReadLine();

if (index.ContainsKey(keyword))
{
foreach (string document in index[keyword])
{
Console.WriteLine(document);
}
}
else
{
Console.WriteLine("Not found!");
}
Console.ReadKey(true);

Таким образом, нет необходимости искать в каждом документе ключевое слово каждый раз, когда пользователь хочет найти слово. Ключевое слово просто находится в индексе (если оно существует), и список документов, которые его содержат, сразу же доступен:

indexingsearch-indexout

Это было простым доказательством того, как работает индексирование и поиск, но вот несколько дополнительных замечаний:

  • Индекс обычно создается по мере добавления в него документов, а затем сохраняется в одном или нескольких файлах (в отличие от этой программы, где индекс перестраивается при каждом запуске программы — это просто для упрощения иллюстрации).
  • Такие слова, как «и» и «the», которые очень распространены, называются  стоп-словами  и обычно исключаются из индекса.
  • Обычной практикой является сделать поиск нечувствительным к регистру, например, путем преобразования индексированных слов и ключевых слов запроса в нижний регистр.

В этой статье представлена ​​концепция индексации и то, как она используется для поиска по одному ключевому слову. Хотя в текстовом поиске используются и другие методы, индексирование, безусловно, является одним из наиболее важных и имеет множество приложений, включая базы данных и поиск текста (например, поисковые системы). Фундаментальная концепция, которую следует помнить, заключается в том, что весь смысл индексации заключается в быстром поиске!

34
Share: