Эта статья была первоначально опубликована как « Индексирование и поиск (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». Концептуально, мы говорим об этом:
Сделать это в 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 и протестируете эту программу, вы увидите, что она работает:
Однако этот метод не годится, потому что он займет больше времени, поскольку документы становятся больше (больше слов) и более многочисленными (больше документов).
Правильный способ быстрой обработки поисковых запросов — это создание индекса. Это будет выглядеть примерно так:
В индексе хранится список всех слов, каждое из которых содержит список документов, которые его содержат. Если вы сравните его с первой диаграммой, вы заметите, что мы изменили отображение слов и документов; Вот почему мы называем это инвертированным индексом .
Мы можем сделать это в 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);
Таким образом, нет необходимости искать в каждом документе ключевое слово каждый раз, когда пользователь хочет найти слово. Ключевое слово просто находится в индексе (если оно существует), и список документов, которые его содержат, сразу же доступен:
Это было простым доказательством того, как работает индексирование и поиск, но вот несколько дополнительных замечаний:
- Индекс обычно создается по мере добавления в него документов, а затем сохраняется в одном или нескольких файлах (в отличие от этой программы, где индекс перестраивается при каждом запуске программы — это просто для упрощения иллюстрации).
- Такие слова, как «и» и «the», которые очень распространены, называются стоп-словами и обычно исключаются из индекса.
- Обычной практикой является сделать поиск нечувствительным к регистру, например, путем преобразования индексированных слов и ключевых слов запроса в нижний регистр.
В этой статье представлена концепция индексации и то, как она используется для поиска по одному ключевому слову. Хотя в текстовом поиске используются и другие методы, индексирование, безусловно, является одним из наиболее важных и имеет множество приложений, включая базы данных и поиск текста (например, поисковые системы). Фундаментальная концепция, которую следует помнить, заключается в том, что весь смысл индексации заключается в быстром поиске!