Нечувствительное к регистру троичное дерево поиска

Некоторое время я использовал Ternary Search Tree в качестве структуры данных для реализации выпадающего списка со списком автозаполнения. Это означает, что когда пользователь вводит "fo", выпадающее поле со списком будет отображаться

фу фуд футбол

Проблема в том, что мое текущее использование Ternary Search Tree чувствительно к регистру. Моя реализация заключается в следующем. Он использовался в реальном мире около 1++ лет. Следовательно, я считаю это довольно надежным.

Код моего троичного дерева поиска

Тем не менее, я ищу нечувствительное к регистру дерево троичного поиска, что означает, что когда я набираю "fo", выпадающий список покажет мне

foO Food fooTBall

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

    /** 
 * Stores value in the TernarySearchTree. The value may be retrieved using key.
 * @param key A string that indexes the object to be stored.
 * @param value The object to be stored in the tree.
 */    
public void put(String key, E value) {
    getOrCreateNode(key).data = value;
}

/**
 * Retrieve the object indexed by key.
 * @param key A String index.
 * @return Object The object retrieved from the TernarySearchTree.
 */
public E get(String key) {
    TSTNode<E> node = getNode(key);
    if(node==null) return null;
    return node.data;
}

Пример использования следующий. TSTSearchEngine использует TernarySearchTree в качестве основной магистрали.

Пример использования троичного дерева поиска

// There is stock named microsoft and MICROChip inside stocks ArrayList.
TSTSearchEngine<Stock> engine = TSTSearchEngine<Stock>(stocks);
// I wish it would return microsoft and MICROCHIP. Currently, it just return microsoft.
List<Stock> results = engine.searchAll("micro");
Источник

3 ответа

Решение

Один из ключевых факторов, которые затрудняют поддержку моего текущего троичного дерева поиска для поиска без учета регистра, состоит в том, что моя базовая структура данных - это сопоставление "один к одному". Пожалуйста, посмотрите на следующий тестовый код:

public void testPut() {
    System.out.println("put");
    Name name0 = new Name("abc");
    Name name1 = new Name("abc");
    TernarySearchTree<Name> instance = new TernarySearchTree<Name>();
    instance.put(name0.toString(), name0);
    instance.put(name1.toString(), name1);
    assertEquals(2, instance.matchPrefix("a").size()); // fail here. Result is 1
}

Мое текущее краткосрочное решение заключается в том, что я использую TSTSearchEngine, чтобы обернуть все TernarySearchTree. TSTSearchEngine состоит из

(1) TernarySearchTree, предоставляющий ключ UPPER-CASE для сопоставления.

(2) Карта String-To-ArrayList.

Вот что происходит, когда я выступаю:

TSTSearchEngine<Name> engine = TSTSearchEngine<Name>();
engine.put(name0); // name0 is new Name("Abc");
engine.put(name1); // name0 is new Name("aBc");

(1) name0.toString () будет преобразовано в верхний регистр ("ABC"). Он будет вставлен в TernarySearchTree. "ABC" будет и ключом, и значением для TernarySearchTree.

(2) "ABC" будет использовать в качестве ключа для карты, чтобы вставить name0 в список массивов.

(3) name1.toString () будет преобразовано в верхний регистр ("ABC"). Он будет вставлен в TernarySearchTree. S1 будет и ключом, и значением для TernarySearchTree.

(4) "ABC" будет использовать в качестве ключа для карты, чтобы вставить name1 в список массивов.

Когда я пытаюсь

engine.searchAll("a");

(1) TernarySearchTree вернет "ABC".

(2) "ABC" будет использоваться в качестве ключа для доступа к карте. Карта вернет список массивов, который содержит name0 и name1.

Это решение работает. Пример кода можно сослаться на образец кода для нового TSTSearchEngine

Однако это может быть неэффективным решением, так как требует двухпроходного поиска. Я обнаружил, что есть реализация в C++ C++ Реализация без учета регистра троичного дерева поиска. Следовательно, есть возможность, что код C++ может быть перенесен на Java.

Источник

Я раньше не использовал TST, но разве это не так просто, как нижний или верхний регистр ключей, как во время хранения, так и во время поиска? Из вашего фрагмента кода похоже, что это должно работать.

Источник

Я реализовал троичное дерево поиска, вы можете взглянуть на http://kunalekawde.blogspot.com/2010/05/radix-patricia-and-ternary.html В случае нечувствительности к регистру, либо вы отображаете маленькие буквы и заглавные буквы в одно шестнадцатеричное / десятичное значение или при получении префикса проверьте значение.

Источник
Другие вопросы по тегам