Java: лучший способ найти слово в алфавитном отсортированном текстовом файле - PullRequest
3 голосов
/ 05 марта 2012

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

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

Мне интересно, можно ли читать строки, пока я не достигну n 'ая строка, проверка правильности термина и выполнение действий в соответствии с алгоритмом бинарного поиска (возможно, чтение строк снова, потому что мне нужна строка, которую я уже пропустил) более эффективна, чем просто проверка терминов строка за строкой?

Любые другие предложения также приветствуются!

Обратите внимание, что мне нужно получить набор строк, в зависимости от набора условий для поиска.

Ответы [ 2 ]

5 голосов
/ 05 марта 2012

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

Если вы действительно хотите сделать это самостоятельно, вам нужно создать два отдельных индекса:

  • Индекс слова -> номеров строк, содержащих термин, чтобы вы могли быстро рассчитать набор номеров строк, содержащих данный поисковый термин
  • Индекс номера строки -> позиция в файле, чтобы вы могли быстро получить нужную строку с помощью произвольного доступа

Кроме того, если ваш набор данных действительно велик, то оба этих индекса могут сами по себе быть больше, чем память . Таким образом, вам придется реализовать дисковый индекс - что-то вроде B-Tree . В этот момент вы будете заново изобретать большую часть колеса СУБД и, возможно, ударить себя за то, что не используете надлежащую базу данных.

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

1 голос
/ 05 марта 2012

Строковое чтение файла будет неэффективным, да, особенно с учетом размера используемого вами корпуса. Рассматривали ли вы индексацию данных в чем-то, кроме плоского файла? Как база данных, которая может быть запрошена? Или использовать инструмент, такой как Lucene, для индексации и поиска данных?

...