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

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

3 голосов
/ 06 марта 2009

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

Foo питание футбол

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

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

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

Foo питание ФУТБОЛЬНЫЙ

Вот некоторые ключевые интерфейсы для 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 ]

3 голосов
/ 10 марта 2009

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

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.

1 голос
/ 06 марта 2009

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

0 голосов
/ 20 мая 2010

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

...