Java: Лучший способ найти слово в алфавитном отсортированном текстовом файле

Question

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

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

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

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

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

Answer 1

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

Answer 2

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

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

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

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

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