Как реализовать простую функцию автозаполнения?

Я хотел бы реализовать простой класс (на Java), который позволил бы мне регистрировать и отменять регистрацию строк, а также на основе текущего набора строк автоматически заполнять заданную строку. Итак, интерфейс будет таким:

  • пустое добавление (строка)
  • недействительно удалить (строка)
  • Строка завершена (строка)

Как лучше всего это сделать с точки зрения алгоритмов и структур данных?


java autocomplete
person Kaarel    schedule 16.09.2008    source источник
comment
что делать, если complete() неоднозначно?   -  person maccullt    schedule 16.09.2008
comment
complete() является однозначным в том смысле, что он завершится только до точки, где начинается неоднозначность (т. е. он вернет не зарегистрированную строку, а общий префикс некоторых зарегистрированных строк). Однако может быть другой метод, который вернет список зарегистрированных строк.   -  person Kaarel    schedule 16.09.2008

Ответы (6)


arrow_upward
4
arrow_downward

вам следует рассмотреть возможность использования PATRICIA trie для структуры данных. Поищите в гугле «патриция трие», и вы найдете много информации...

person pgras    schedule 16.09.2008
comment
Фантастическое предложение, я никогда не слышал о PATRICIA trie. Определенно, я собираюсь провести дополнительное исследование, - person Aidos; 16.09.2008
comment
Спасибо за ответ. В итоге я использовал эту Java-реализацию radix-деревьев: code.google.com/p/radixtree - person Kaarel; 17.09.2008

arrow_upward
3
arrow_downward

Структура данных, которая вам нужна, называется троичным деревом поиска.

Отличный пример JavaWorld можно найти по адресу www.javaworld.com/javaworld/jw-02-2001/jw-0216-ternary.html.

person Aidos    schedule 16.09.2008

arrow_upward
0
arrow_downward

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

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

person johnmcase    schedule 16.09.2008

arrow_upward
0
arrow_downward

Для тех, кто наткнется на этот вопрос...

Я только что опубликовал реализацию автозаполнения на стороне сервера в Google Code. Проект включает библиотеку Java, которую можно интегрировать в существующие приложения, и автономный сервер автозаполнения HTTP AJAX.

Я надеюсь, что это позволит людям включить эффективное автозаполнение в свои приложения. Ударь по шинам!

person Community    schedule 22.12.2009

arrow_upward
0
arrow_downward

Я создал плагин JQuery под названием Simple AutoComplete, который позволяет вам добавлять множество автозаполнений по своему усмотрению на одной странице, добавлять фильтры с дополнительными параметрами и выполнять функцию обратного вызова для получения других параметров, таких как идентификатор элемента.

См. его по адресу http://www.idealmind.com.br/projetos/simple-autocomplete-jquery-plugin/

person Wellington RIbeiro    schedule 22.03.2010

arrow_upward
-2
arrow_downward

Обычные выражения.

person Jon Homan    schedule 16.09.2008