Как реализовать простую функцию автозаполнения?
Я хотел бы реализовать простой класс (на Java), который позволил бы мне регистрировать и отменять регистрацию строк и на основе текущего набора строк автоматически заполнять данную строку. Итак, интерфейс будет таким:
- void add (строка)
- void remove (строка)
- Строка завершена (Строка)
Как лучше всего это сделать с точки зрения алгоритмов и структур данных?
complete () однозначен в том смысле, что он будет завершен только до точки, где начинается неоднозначность (т.е. он не вернет зарегистрированную строку, а общий префикс некоторых зарегистрированных строк). Однако может быть другой метод, который вернет список зарегистрированных строк.
Ответы 6
Обычные выражения.
Это должен быть какой-то список, который вы можете поддерживать в отсортированном порядке. Вам также придется написать свой собственный алгоритм поиска, который даст вам индекс первого элемента в списке, который соответствует вашему шаблону поиска. Затем выполняйте итерацию от этого индекса до первого несоответствующего элемента и получения списка возможных завершений.
Я бы посмотрел на TreeList из commons-collection. Он имеет быстрое время вставки и удаления из середины списка, которое вам нужно, чтобы поддерживать отсортированный порядок. Вероятно, было бы довольно легко написать свою функцию поиска на основе дерева, лежащего в основе этого списка.
Структура данных, которую вы ищете, называется троичным деревом поиска.
На www.javaworld.com/javaworld/jw-02-2001/jw-0216-ternary.html есть отличный пример JavaWorld.
вам следует подумать об использовании дерева PATRICIA для структуры данных. Поищите в Google "patricia trie", и вы найдете много информации ...
Замечательное предложение, я никогда не слышал о PATRICIA trie. Определенно тот, над которым я собираюсь провести еще несколько исследований,
Спасибо за ответ. В итоге я использовал эту Java-реализацию оснований счисления: code.google.com/p/radixtree
Для тех, кто наткнулся на этот вопрос ...
Я только что разместил реализация автозаполнения на стороне сервера в Google Code. Проект включает java-библиотеку, которая может быть интегрирована в существующие приложения, и автономный HTTP-сервер автозаполнения AJAX.
Я надеюсь, что это позволит людям включить эффективное автозаполнение в свои приложения. Убей шины!
Я создал плагин JQuery под названием Simple AutoComplete, который позволяет вам добавлять много автозаполнений по вашему желанию на той же странице, а также добавлять фильтры с дополнительными параметрами и выполнять функцию обратного вызова для получения других параметров, таких как идентификатор элемента.
Смотрите на http://www.idealmind.com.br/projetos/simple-autocomplete-jquery-plugin/
что, если complete () неоднозначно?