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

Question

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

Foo пищи футбол

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

My Ternary Search Tree code

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

Foo Food ФУТБОЛЬНЫЙ

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

Example usage of Ternary Search Tree

// 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"); 

Answer 1

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

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) Карта с строкой в ​​массив.

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

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» будет использоваться в качестве ключа для карты, чтобы вставить имя0 в список массивов.

(3) имя1.toString() преобразуется в UPPER-CASE ("ABC"). Он будет вставлен в TernarySearchTree. S1 будет ключом и значением для TernarySearchTree.

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

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

engine.searchAll("a"); 

(1) TernarySearchTree возвращает "ABC".

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

Данное решение работает. Код примера можно отнести к Sample Code for New TSTSearchEngine

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

Answer 2

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

Answer 3

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