Код C # / Алгоритм поиска текста по терминам

Question

У нас есть 5 МБ типичного текста (просто простые слова). У нас есть 1000 слов / фраз для использования в качестве терминов для поиска в этом тексте.

Какой самый эффективный способ сделать это в .NET (в идеале C #)?

Наши идеи включают в себя регулярные выражения (один, их много) и даже String.Contains.

Вводится текстовая строка размером от 2 МБ до 5 МБ - весь текст. Многократные хиты хороши, так как в каждом семестре (из 1000), который соответствует, мы хотим знать об этом. Производительность с точки зрения всего времени выполнения, не волнует след. Текущий алгоритм дает около 60 секунд +, используя наивный string.contains. Мы не хотим, чтобы «кошка» соответствовала «категории» или даже «кошкам» (т. Е. Слово «целое» должно попадать, а не основываться на).

Мы ожидаем, что коэффициент попадания <5% в тексте. Результатом в идеале должны быть просто совпадающие термины (пока вам не нужна позиция или частота). Мы получаем новую строку 2-5 МБ каждые 10 секунд, поэтому не можем предполагать, что мы можем индексировать входные данные. 1000 терминов являются динамическими, хотя скорость изменения составляет около 1 в час. </p>

Answer 1

Наивная строка. Содержит 762 слова (последняя страница) «Войны и мира» (3,13 МБ). Переключение на 1000 идентификаторов GUID выполняется за 5,5 с.

Regex.IsMatch обнаружил 762 слова (большая часть которых, вероятно, была и на более ранних страницах) примерно за 0,5 секунды и исключил GUID через 2,5 секунды.

Я бы предположил, что ваша проблема лежит в другом месте ... Или вам просто нужно приличное оборудование.

Answer 2

Зачем изобретать велосипед? Почему бы просто не использовать что-то вроде Lucene.NET ?

Answer 3

рассматривали ли вы следующее:

1. Вы заботитесь о подстроке? Допустим, я ищу слово «кот», ни больше, ни меньше. Теперь рассмотрим алгоритм Кнута-Морриса-Пратта или string.contains для "concatinate". оба они вернут истину (или индекс). это нормально?

2. Также вам придется взглянуть на идею «конечного» или «конечного» состояния слова. давайте снова посмотрим на «дневник», тестовая отправка «есть много видов дневников». хорошо для вас и меня у нас есть слово "дневники" это считается? если это так, нам нужно предварительно обработать пересылку, преобразовав слова в конечное состояние (дневники -> дневник), пересылка станет «существует много видов дневников». Теперь мы можем сказать, что Дневник находится в стороже (пожалуйста, посмотрите на портье Stemmer Algroithm)

3. Также, когда дело доходит до обработки текста (он же Natrual Langauge Processing), вы можете удалить некоторые слова как шум, например, «a, есть, вы, я, я, некоторые, чтобы» <- это может быть считаются бесполезными словами, и могут ли быть удалены перед какой-либо обработкой? например </p>

«Я написал немного C # сегодня», если бы у меня было 10 000 ключевых работ, чтобы найти, мне нужно было бы отсканировать всю отправку, 10000 х количество слов в отправке. удаление шума до того, как рука сократит время обработки

«написано на C # сегодня» <- убрал шум, теперь есть намного меньше, чтобы посмотреть. </p>

Отличную статью о НЛП можно найти здесь. Сравнение отправлений

НТН

Кости

Answer 4

Как это работает в сравнении? Он использует LINQ, поэтому он может быть немного медленнее, не уверен ...

List<String> allTerms = new List<String>(new String(){"string1", "string2", "string3", "string4"});
List<String> matches = allTerms.Where(item => Regex.IsMatch(bigTextToSearchForTerms, item, RegexOptions.IgnoreCase));

Для реализации метода FIND используются классические предикаты, поэтому он должен быть быстрее, чем LINQ:

static bool Match(string checkItem)
{
  return Regex.IsMatch(bigTextToSearchForTerms, checkItem, RegexOptions.IgnoreCase);
}

static void Main(string[] args)
{
  List<String> allTerms = new List<String>(new String(){"string1", "string2", "string3", "string4"});
  List<String> matches = allTerms.Find(Match);
}

Или это использует лямбда-синтаксис для реализации классического предиката, который снова должен быть быстрее, чем LINQ, но более читаемым, чем предыдущий синтаксис:

List<String> allTerms = new List<String>(new String(){"string1", "string2", "string3", "string4"});
List<String> matches = allTerms.Find(checkItem => Regex.IsMatch(bigTextToSearchForTerms, checkItem, RegexOptions.IgnoreCase));

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

Answer 5

Хорошо, текущая переделка показывает это как самый быстрый (psuedocode):

foreach (var term in allTerms)
{
    string pattern = term.ToWord(); // Use /b word boundary regex
    Regex regex = new Regex(pattern, RegexOptions.IgnoreCase);
    if (regex.IsMatch(bigTextToSearchForTerms))
    {                    
        result.Add(term);                                        
    }
}

Что было удивительно (по крайней мере для меня!), Так это то, что выполнение регулярного выражения в 1000 раз было быстрее, чем одного регулярного выражения с 1000 альтернативами, то есть "/ b term1 / b | / b term2 / b | / b termN / b" а затем пытается использовать regex.Matches.Count

Answer 6

Это узкое место? Сколько времени это занимает? 5 MiB на самом деле не так много данных для поиска. Регулярные выражения могут работать очень хорошо, особенно если вы кодируете все строки поиска в шаблон one , используя чередования. Это в основном амортизирует общую стоимость поиска до O (n + m), где n - длина вашего текста, а m - длина всех шаблонов, вместе взятых. Обратите внимание, что это очень хорошая производительность.

Альтернативой, которая хорошо подходит для многих паттернов, является алгоритм Wu Manber . Я уже опубликовал очень упрощенную реализацию C ++ алгоритма.

Answer 7

Вот еще одна идея: сделать класс примерно таким:

class Word
{
    string Word;
    List<int> Positions;
}

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

Затем составьте еще два списка, которые будут служить индексами. Один будет хранить все эти классы, отсортированные по их текстам, другой - по их позициям в тексте. По сути, текстовый индекс, вероятно, будет SortedDictionary, тогда как индекс позиции будет простым List<Word>.

Затем, чтобы найти фразу, вы разделяете эту фразу на слова. Найдите первое слово в словаре (это O (log (n))). Оттуда вы знаете возможные слова, которые следуют за ним в тексте (они у вас есть из массива Positions). Посмотрите на эти слова (используйте индекс позиции, чтобы найти их в O (1)) и продолжайте, пока не найдете одно или несколько полных совпадений.

Answer 8

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

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

Наиболее эффективный подход, который я могу себе представить, - это динамическое построение шаблона соответствия с использованием списка, а затем использование регулярных выражений. Гораздо проще вести список из 1000 элементов, чем поддерживать шаблон регулярного выражения, основанный на тех же 1000 элементах.

Насколько я понимаю, Regex использует тот же алгоритм KMP, который был предложен для эффективной обработки больших объемов данных - поэтому, если вам действительно не нужно копаться и разбираться в деталях, как это работает (что может быть полезно для личного роста), тогда возможно, регулярное выражение будет в порядке.

Здесь есть довольно интересная статья об алгоритмах поиска для многих шаблонов в больших файлах: http://webglimpse.net/pubs/TR94-17.pdf

Answer 9

Модифицированное Суффиксное дерево было бы очень быстрым, хотя это заняло бы много памяти, и я не знаю, как быстро это было бы построить. Однако после этого каждый поиск будет занимать O (1).