подсчет (большое количество) строк в (очень большом) тексте

Question

Я видел несколько вариантов вопроса «эффективно искать строки в файле (файлах)» в Stackoverflow, но не совсем как в моей ситуации.

• У меня есть один текстовый файл, который содержит относительно большое количество (> 300 КБ) строк.Подавляющее большинство этих строк представляют собой несколько слов (например, «Плесси против Фергюсона», «Джон Смит» и т. Д.).

• Оттуда мне нужно искать черезочень большой набор текстовых файлов (набор юридических документов объемом более 10 ГБ) и подсчет экземпляров этих строк.

Из-за количества строк поиска, строк, содержащих несколько слов, и размера цели поиска, многие "стандартные" решения кажутся несостоятельными.

Некоторые вещи немного упрощают проблему -

• Мне не нужны сложные токенизации / стемминги / и т. Д. (Например, единственные, что меня волнует, это "Plessy vФергюсон ", не нужно беспокоиться о" Плесси "," Плесси и др. "И т. Д.)

• будут некоторые дубликаты (например, несколько человек по имени«Джон Смит»), однако, это не очень статистически значимая проблема для этого набора данных, так что ... если несколько Джона Смита объединяются в один подсчет, это нормально.

• Мне нужно только сосчитать эти конкретные случаи;Мне не нужно возвращать результаты поиска

• 10 экземпляров в 1 файле считаются так же, как 1 экземпляр в каждом из 10 файлов

Любыепредложения по быстрым / грязным способам решения этой проблемы?

Я исследовал NLTK, Lucene и других, но они кажутся излишними для проблемы, которую я пытаюсь решить.Должен ли я смириться с этим и импортировать все в БД?брутфорс grep это 300к раз?;)

Мой предпочтительный инструмент разработки - это Python.

---

Документы, которые нужно искать, в основном являются легальными документами, подобными этим - http://www.lawnix.com/cases/plessy-ferguson.html

Ожидаемые результаты - подсчетза то, как часто дело упоминается в этих документах - «Плесси против Фергюсона: 15»

Answer 1

Простой способ решить эту проблему - создать три с помощью ваших запросов (просто дерево префиксов, список узлов с одним символом внутри), и при поиске в файле 10 ГБ вы рекурсивно просматриваете дерево в виде текста. Матчи.

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

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

Answer 2

Вы должны использовать алгоритмы сопоставления с образцом группы, которые используют динамические алгоритмы для повторного использования оценки.Т.е. Ахо-Корасик.Реализации

• http://code.google.com/p/graph-expression/wiki/RegexpOptimization
• http://alias -i.com / lingpipe / docs / api / com / aliasi / dict / ExactDictionaryChunker.html

Answer 3

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

Разделите файлы для поиска на числа разумного размера 10/100/1000 ... и длякаждый «чанк» использует индексирующий SW, доступный для SW.Здесь я имею в виду ctags gnu global или, возможно, утилиту ptx или использование техники, описанной в этом SO сообщении .

Используя эту технику, вам «только» нужно искать в индексных файлах целевые строки.

Answer 4

Уродливое решение о грубой силе не сработает.

Определите время выполнения одного grep для ваших документов и экстраполируйте время, необходимое для 300k greps (и, возможно, попробуйте распараллелить его, если у вас есть много доступных машин), возможно ли это?Я предполагаю, что поиск в 300 тысяч не будет осуществим.Например, поиск по ~ 50 МБ файлов занял у меня около 5 с, поэтому для 10 Гбайт вы ожидаете ~ 1000 с, а затем повторение 300 000 раз означает, что с одним компьютером вы справитесь примерно за 10 лет.Вы можете распараллелить, чтобы получить некоторые улучшения (ограниченные диском io на одном компьютере), но все еще будут весьма ограничены.Я предполагаю, что вы хотите, чтобы задача была выполнена за часы, а не за месяцы, так что это вряд ли решение.

Так что вам нужно как-то проиндексировать документы.Lucene (скажем, через pythonsolr) или Xapian должны подходить для ваших целей.Индексируйте документы, затем ищите проиндексированные документы.

Answer 5

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

1. Жесткий диск IO
2. Память
3. Время обработки

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

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

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