Как реализовать автозаполнение массивного набора данных
Мне потребовалось немного времени, чтобы разобраться. Настоящим ключом является чтение документации Formatter.
// Get your data from wherever.
final byte[] data = getData();
// Get the digest engine.
final MessageDigest md5= MessageDigest.getInstance("MD5");
// Send your data through it.
md5.update(data);
// Parse the data as a positive BigInteger.
final BigInteger digest = new BigInteger(1,md5.digest());
// Pad the digest with blanks, 32 wide.
String hex = String.format(
// See: http://download.oracle.com/javase/1.5.0/docs/api/java/util/Formatter.html
// Format: %[argument_index$][flags][width]conversion
// Conversion: 'x', 'X' integral The result is formatted as a hexadecimal integer
"%1$32x",
digest
);
// Replace the blank padding with 0s.
hex = hex.replace(" ","0");
System.out.println(hex);
5 ответов
Как я указал в том, Как реализовать возрастающий поиск в списке, необходимо использовать структуры как Trie или Patricia trie для поиска шаблонов в крупных текстах.
И для обнаружения шаблонов посреди некоторого текста существует одно простое решение. Я не уверен, является ли это наиболее эффективное решение, но я обычно делаю это следующим образом.
Когда я вставляю некоторый новый текст в Trie, я просто вставляю его, затем удаляю первый символ, вставляю снова, удаляю второй символ, вставляю снова... и так далее, пока целый текст не используется. Затем можно обнаружить каждую подстроку каждого вставленного текста всего одним поиском от корня. Ту получающуюся структуру называют Суффиксным деревом и существует большая доступная оптимизация.
И это действительно невероятно быстро. Найти все тексты, которые содержат данную последовательность n символов, которые необходимо осмотреть в большинстве n узлов и выполнить поиск в списке детей для каждого узла. В зависимости от реализации (массив, список, двоичное дерево, пропускает список) дочернего набора узла, Вы смогли отождествлять необходимый дочерний узел только с 5 поисковыми шагами, принимающими нечувствительные к регистру латинские буквы только. Вид интерполяции мог бы быть полезным для больших алфавитов и узлов со многими детьми как обычно находимые около корня.
Не пытайтесь реализовать это сами (если Вам не просто любопытно). Используйте что-то как Lucene или Endeca - он сэкономит Вам время и волосы.
Не алгоритмически связанный с тем, что Вы спрашиваете, но удостоверяетесь, что у Вас есть 200 мс или больше задержки (задержка) после нажатия (нажатий) клавиши, таким образом, Вы удостоверяетесь, что пользователь прекратил вводить прежде, чем выпустить асинхронный запрос. Тем путем Вы уменьшите избыточные запросы HTTP до сервера.
Я использовал бы что-то вроде trie и имел бы значение каждой вершины быть списком возможностей, которые содержат слово, представленное вершиной. Вы могли отсортировать их в порядке вероятности или динамично сортировать/фильтровать их на основе других слов, пользователь ввел в поле поиска и т.д. Это выполнится очень быстро и в разумной сумме RAM.
Вы сохраняете объекты на стороне сервера (возможно, в DB, если набор данных является действительно большим и сложным), и Вы отправляете вызовы Ajax от браузера клиента, которые возвращают результаты с помощью json/xml. Можно сделать это в ответ на пользователя, вводящего, или с таймером.