Как сделать поиск по шаблону быстрее? - PullRequest
9 голосов
/ 21 октября 2010

Я работаю с инкрементным файлом размером около 1 ГБ и хочу найти определенный шаблон. В настоящее время я использую регулярные выражения Java, есть ли у вас идеи, как я могу сделать это быстрее?

Ответы [ 4 ]

8 голосов
/ 21 октября 2010

Звучит как работа для Apache Lucene .

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

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

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

7 голосов
/ 05 июня 2011

В основном вам нужен конечный автомат, который может обрабатывать поток.Этот поток ограничен файлом ... Каждый раз, когда файл увеличивается, вы читаете то, что было добавлено к нему (например, команду tail linux, которая добавляет к стандартному выводу строки, добавленные в файл).

Есливам нужно остановить / перезапустить ваш анализатор, вы можете либо просто сохранить где-нибудь начальную позицию (которая может зависеть от окна, которое вам нужно для сопоставления с образцом), и перезапустить его.Или вы можете перезапустить с нуля.

Это для части проблемы "увеличение файла".

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

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

4 голосов
/ 05 июня 2011

Я думаю, что это зависит от:

  • структуры ваших данных (ориентированных на линии?)
  • сложности совпадения
  • скорости, с которойфайл данных растет

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

Это особенно помогает, если данные не растут слишком быстро.

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

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

4 голосов
/ 21 октября 2010

Вы можете попробовать использовать классы Pattern и Matcher для поиска по скомпилированным выражениям.

См. http://download.oracle.com/javase/1.4.2/docs/api/java/util/regex/Pattern.html и http://download.oracle.com/javase/tutorial/essential/regex/

или используйте вашу любимую поисковую систему для поиска по терминам:

Оптимизация Java регулярных выражений или

производительность регулярных выражений Java

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...