Как обрабатывать содержимое файла как String

Question

Я создаю игру Scrabble, в которой используется словарь. Для эффективности вместо загрузки всего словаря (через txt-файл) в структуру данных (набор, список и т. Д.) Есть какой-либо встроенный класс java, который может помочь мне обработать содержимое файла как строку.

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

Ребята, вы хоть представляете, что я смогу сделать. Если файл словаря должен быть в чем-то ином, чем текстовый файл (например, XML-файл), я открыт, чтобы попробовать и это.

ПРИМЕЧАНИЕ: я не ищу http://commons.apache.org/io/api-1.4/org/apache/commons/io/FileUtils.html#readFileToString%28java.io.File%29

Этот метод не является частью API Java.

HashSet не пришёл в голову, я застрял в мысли, что все методы содержат () использовали O (n) раз, спасибо Божо за то, что он со мной это выяснил, похоже, что я буду использовать HashSet.

Answer 1

Я думаю, что ваш лучший вариант - загрузить их все в память, в HashSet.Там contains(word) - это O (1).

Если у вас все в порядке с тем, что он находится в памяти, его значение как String для вызова contains(..) гораздо менее эффективно, чем HashSet.

И я должен упомянуть другой вариант - есть структура данных для представления словарей - она ​​называется Trie.Вы не можете найти реализацию в JDK.

Очень грубый расчет говорит о том, что для всех английских слов (1 миллион) вам потребуется ~ 12 мегабайт оперативной памяти.что в несколько раз меньше, чем стандартные настройки памяти JVM.(1 миллион * 6 букв в среднем * 2 байта на букву = 12 миллионов байтов, что составляет ~ 12 мегабайт).(Ну, может быть, немного больше для хранения хэшей)

Если вы действительно настаиваете на том, чтобы не читать его в памяти, и хотите отсканировать файл на предмет заданного слова, то вы можете использовать java.util.Scanner и его scanner.findWithHorizon(..).Но это было бы неэффективно - я полагаю, O (n) и затраты на ввод / вывод.

Answer 2

Хотя HashSet является вполне приемлемым решением (см. Ответ Божо), существуют и другие структуры данных, которые можно использовать, включая Trie или Heap.

Преимущество Trie Имеется в том, что в зависимости от деталей реализации , начальные префиксные буквы могут быть разделены (в конце концов, дерево также называется «префиксным деревом»).В зависимости от структуры реализации и данных, это может или не может быть улучшением.

Другой вариант, особенно если требуется файловый доступ, заключается в использовании Heap - PriorityQueue Javaна самом деле это куча, но она не основана на файлах, поэтому для этого потребуется найти / сделать реализацию.

Все эти структуры данных (и более) могут быть реализованы на основе файлов (используйте большеIO за поиск - который на самом деле может быть менее общим - но сэкономить память) или реализован напрямую (например, использовать SQLite и позволить ему делать это в B-Tree).SQLite выделяется тем, что он может быть «обычным инструментом» (когда-то часто используемым ;-) в наборе инструментов;Импорт, проверка и модификация данных просты, и «это просто работает».SQLite даже используется в менее мощных системах, таких как Android.

HashSet поставляется "бесплатно" с Java, но нет стандартной реализации Trie или Heap на основе файлов.Я бы начал с HashSet - Reasoning:

1. Dictionary = 5MB.
2. Загружен в HashSet (при условии больших накладных расходов) = 20MB.
3. Использование памяти в отношениина другие вещи = минимальный (предполагается, ноутбук / рабочий стол)
4. Время для реализации с HashSet = 2 минуты.
5. Я потерял только 2 минуты, если я решу, что HashSet не был хорошдостаточно: -)

Счастливое кодирование.

---

Ссылки на случайные реализации структуры данных (могут или не могут быть подходящими):

• TernarySearchTrie Считывает в плоский файл (должен быть специально создан?)
• TrieTree Поддерживает создание файла Trie из плоского файла.Не уверен, что эта Trie работает с диска.
• FileHash Хеш, который использует поддержку файла.
• HashStore Другой дисковый хеш
• WB B-Tree Простая реализация B-дерева / «база данных»
• SQLite Небольшие встроенные СУБД.
• UTF8String Может использоваться для значительного сокращенияТребования к памяти при использовании HashSet<String> при использовании латинского словаря.(Строка в Java использует кодировку UTF-16, которая составляет минимум два байта / символ.)

Answer 3

Вам нужно сжать свои данные, чтобы избежать необходимости хранить все эти слова.Для этого можно использовать дерево, в котором узлами являются буквы, а листья отражают конец слова.Таким образом, вы не сохраняете повторяющиеся данные, такие как the there these, где все эти слова имеют одинаковый префикс.

Существует способ повысить эффективность использования этого решения.(Подсказка: заказ по буквам)

Answer 4

Используйте readline () java.io.BufferedReader.Это возвращает строку.

String line = new BufferedReader (new FileReader (file) ).readline ();