Троичное Дерево Поиска без учета регистра

Question

Я использовал Троичное Дерево Поиска некоторое время в качестве структуры данных реализовывалось выпадающее поле со списком автозаполнения.Это означает, что когда пользователь введет "fo", отобразится выпадающее поле со списком

фу еда футбол

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

Мой троичный код Дерева поиска

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

Фу Еда Футбол

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

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) Троичное поисковое дерево, предоставляющее ключ к карте в верхнем регистре.

(2) Сопоставление строки с 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" будет использоваться в качестве ключа для map, чтобы вставить name0 в список массива.

(3) name1.toString() будет преобразован в ВЕРХНИЙ РЕГИСТР ("ABC").Он будет вставлен в TernarySearchTree.S1 будет одновременно ключом и значением для TernarySearchTree.

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

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

engine.searchAll("a");

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

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

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

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

Answer 2

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

Answer 3

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