Сверхбыстрое автозаполнение с использованием бинарного поиска в отсортированном файле (300000 строк)

Question

В моем приложении для Android я хочу иметь поле ввода с автозаполнением. Количество элементов будет около 300000. Лучшее решение, кажется, состоит в том, чтобы поместить элементы в файл (на SD-карте), по одному элементу в строке, каждая строка будет иметь одинаковое количество символов, чтобы я мог искать конкретный номер строки. , Если пользователь вводит что-то в текстовое поле, я выполняю бинарный поиск (через RandomAccessFile) файла и показываю предложения.

Я хочу, чтобы автозаполнение было очень быстрым (в идеале, до 100 мс, но я думаю, что это невозможно), какие оптимизации я могу сделать?

Обновление 1: Я преобразую вводимые пользователем символы в строчные английские символы (a-z) с пробелами. Таким образом, «A / B» будет преобразовано в «A B», а затем искать.

Uodate 2: Теперь я понял, что мне нужна дополнительная вещь - для поиска подстрок, начинающих слова.

Answer 1

То, что вы ищете, называется TRIE

http://forums.sun.com/thread.jspa?threadID=5295936

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

Answer 2

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

Answer 3

Trie является очевидным ответом, и уже упоминалось, но дополнительно tr13 библиотека может быть тем, на что вы смотрите. Это дружественный сборщик мусора (один необработанный байтовый массив или байтовый буфер), компактный и достаточно быстрый для вашего случая. Ключи обычно являются строками UTF-8, хотя могут быть любыми байтовыми последовательностями. Значения аналогичны, хотя есть и альтернатива для целочисленных переменных (vints), используемых для получения очень компактных поисков String-to-int (особенно для небольшого набора целых).

Answer 4

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

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

Answer 5

Старая тема, но ЭТО ТО, ЧТО ВАМ НУЖНО: Библиотека поиска строк

Я использовал его для своего приложения «Wordlist Pro» для Android, и это действительно быстро.

Answer 6

100 мс достаточно времени. Я думаю, что наибольшее беспокойство вызывают обновления дисплея.

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

Вы можете хранить первые N байтов (4, может быть,?) Строки и смещение файла в главном файле в индексе каждые 32 записи или около того, и выполнять двоичный поиск по всему этому. Затем вы можете линейно искать до 32 записей после того, как бинарный поиск приблизил вас.

Вы можете настроить частоту индекса от 32 записей до любой, что имеет смысл, учитывая вашу среднюю длину строки и размер одного чтения на вашем носителе. Если бы у вас было 512-байтовое чтение файловой системы и 8-байтовые средние строки, то вы бы делали индекс каждые 64 записи и т. Д. Нет большого смысла иметь более одной индексной записи на минимальный размер чтения с диска.

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

Answer 7

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

В этой конкретной (автозаполненной) ситуации вам потребуется Дерево префиксов или его разновидность (объединение нескольких узлов в один или превращение поддеревьев меньше определенного размера).в простой старый отсортированный список слов).

Answer 8

Я бы посоветовал посмотреть, можете ли вы использовать стандартную библиотеку для этой цели.Возможно, Apache Lucene можно использовать в телефонах Android.Если это так, вы можете создать индекс (префикс слова -> идентификатор слова в Android SQL Lite).Вот обсуждение алгоритма, который использует lucene .

Answer 9

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

Answer 10

проверить это http://en.wikipedia.org/wiki/Binary_search_algorithm

в отсортированном файле у вас есть двоичный поиск в худшем случае O (log (n)) следующая лучшая вещь - это какое-то хеш-отображение, которое идет O (1), хотя это сложно для неполных слов и приведет к огромной таблице отображения.