Как быстро найти текстовые данные в большом текстовом файле?

У меня есть словарный запас с разными словами и информацией о них. Его размер составляет около 100 МБ. Однако поиск этого файла занимает очень много времени. Есть ли способ повысить скорость поиска данных? Например, я думал о написании программы, которая бы разделила текстовый файл на 26 различных текстовых файлов (по первой букве слова), а затем программе просто нужно было бы проверить первую букву данного слова и получить файл гораздо меньшего размера для поиска. Улучшит ли это время выполнения программы? Есть ли какие-нибудь эффективные структурированные данные, в которых я мог бы сохранить файл? Например, json. А как насчет баз данных? Я использую Kotlin / Java.

Изменить: до сих пор я просто перебирал весь файл, пока не нашел совпадение. Но, как я уже сказал, размер файла ›100 МБ. Выполнение программы занимает около 5 секунд, и это поиск всего одного слова. В будущем я хочу, чтобы программа легко выполняла поиск 100 слов за миллисекунды, оптимально. Подобно текстовым редакторам, Word ищет слова в своих словарях.


java kotlin database search vocabulary
person Dj Sushi    schedule 26.06.2020    source источник
comment
Улучшит ли это время выполнения программы? хороший способ узнать это на самом деле написать программу и протестировать ее.   -  person Federico klez Culloca    schedule 26.06.2020
comment
что ты уже испробовал? Нет никаких серебряных пуль. Это зависит от ваших требований.   -  person Govinda Sakhare    schedule 26.06.2020
comment
@FedericoklezCulloca да, я знаю, но было бы бессмысленно, если бы есть гораздо лучшее решение, которое я упускаю. Возможно, например, разделение текстового файла word на 26 * 26 различных текстовых файлов (по первым двум буквам). Думаю, я не единственный, кто когда-либо думал об этой механике, так что я, возможно, просто ищу название этой механики или другое, которое будет еще более эффективным.   -  person Dj Sushi    schedule 26.06.2020
comment
Я не уверен, что вы пробовали, но загрузка всего файла в ОЗУ и поиск в нем слова не займет много времени, поэтому немного сложно предложить лучшее решение для того, что вы сделали, если мы этого не сделаем. знаю, что ты сделал.   -  person Federico klez Culloca    schedule 26.06.2020
comment
Кроме того, конечно, может помочь база данных.   -  person Federico klez Culloca    schedule 26.06.2020
comment
@GoviS Я редактировал вопрос.   -  person Dj Sushi    schedule 26.06.2020
comment
разделение на 26 различных текстовых файлов с последующим использованием исполнителя (например, ThreadPool, ForkJoinPool) для ускорения вашего результата, может быть хорошим началом   -  person Hưng Chu    schedule 26.06.2020
comment
@FedericoklezCulloca да, думал загрузить в оперативку. Скорее всего, это было бы гораздо более быстрое решение, но все же не очень эффективное, имо. Есть идеи по поводу структуры данных, которая просто размещалась бы на жестком диске?   -  person Dj Sushi    schedule 26.06.2020
comment
Другая идея, предполагающая, что слова в порядке, - использовать RandomAccessFile для чтения файла с помощью индексного файла, который вы создаете, в котором есть начальная позиция для первого слова, использующего каждую букву. Например: a: 0, b: 2000, c: 5003 и т. Д.   -  person NormR    schedule 26.06.2020

Ответы (6)


arrow_upward
2
arrow_downward

Это зависит от доступной памяти. Если весь словарь может уместиться в памяти без снижения производительности, тогда HashMap (если каждое слово имеет связанное значение) или HashSet (если нет) специально оптимизированы для быстрого доступа к поиску. Если сохранение всего в памяти невозможно, вы можете использовать базу данных с индексом слов, которые вы хотите найти. Apache Derby - это легкая база данных, прекрасно взаимодействующая с Java, но HSQLDB, H2 или SQLite также являются хорошим выбором.

person Serge Ballesta    schedule 26.06.2020

arrow_upward
1
arrow_downward

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

person Ian Fernandes    schedule 26.06.2020

arrow_upward
1
arrow_downward

Есть несколько способов добиться этого:

  1. Загрузите данные в реляционную базу данных (mysql, Postgres и т. Д.) С одним столбцом, представляющим слово, и другими столбцами, содержащими информацию о слове. Добавьте указатель в столбец слов. Это подойдет для случая, когда ваш набор данных будет увеличиваться в будущем за пределами выделенной памяти.
  2. Загрузите данные в память в хеш-таблицу с ключом в качестве слова и значением в качестве информации о слове.
  3. Если вы хотите написать свою собственную логику, вы можете загрузить данные в список, отсортировать по словам и выполнить бинарный поиск.
person Community    schedule 26.06.2020

arrow_upward
0
arrow_downward

А как насчет баз данных?

Вы можете использовать индексатор, если при поиске вы не хотите выполнять поиск по всем строкам и у вас большая таблица. При создании индекса по таблице СУБД обычно создает B-дерево. B-дерево полезно для хранения большого количества данных, когда вам нужен поиск или поиск по диапазону. Проверьте это сообщение ссылку и ссылку для MySQL ссылка. Если вы хотите узнать больше о том, как реализовать такую ​​структуру, как B-дерево или B + -дерево, вы можете использовать эту книгу ссылка. У вас есть реализация структур, которые используются для поиска данных, здесь у вас нет B-деревьев, но автор является создателем красно-черных деревьев (B-деревья являются обобщением). У вас также есть кое-что здесь ссылка.

person Lazar Đorđević    schedule 26.06.2020

arrow_upward
0
arrow_downward

Вы можете использовать базы данных текстового поиска, такие как ElasticSearch или Apache Solr.

person Community    schedule 26.06.2020

arrow_upward
0
arrow_downward

  • У вас есть файл, в этом файле вы ищите символ за символом и слово за словом
  • Предполагая, что у вас есть n слов в файлах
  • Полная проверка займет n * time_for_one_word_check
  • Предполагая, что time_for_one_word_check является постоянным, мы просто сосредоточимся на n
  • Поиск в отсортированном списке слов с использованием двоичного поиска (или какой-либо его формы) займет самое большее время примерно log (n).
  • Это означает, что если у вас n = 10, полное сканирование займет 10, а двоичный поиск займет 3
  • Для n = 1000000 полное сканирование займет 1000000, а двоичный поиск - 6.
  • Итак, отсортируйте данные и сохраните их, затем выполните поиск в отсортированных данных.
  • Это можно сделать несколькими способами.
  • Сохранение данных в отсортированном формате
  • Вы можете сохранить данные в один файл или сохранить, индексировать и запрашивать эти данные в базе данных.
  • Вам следует выбрать базу данных, если ваши данные станут больше и будут иметь дополнительную сложность позже или если вы собираетесь иметь возможность искать (индексировать) как слова, так и их информацию.
  • Вам следует выбрать простой файл, если не ожидается увеличения объема или сложности данных.
  • Существуют разные форматы файлов, я предлагаю вам попробовать сохранить данные в формате json, где ключи - это отсортированные слова, а значения - их описание (это позволяет вам искать только ключи)
  • Загрузите эти данные один раз при запуске приложения в неизменяемую переменную реализации карты.
  • Запрашивайте эту переменную каждый раз, когда вам нужно выполнить поиск

Полезные ключевые слова для исследования

person sero    schedule 26.06.2020