대소 문자를 구별하지 않는 Ternary 검색 트리

Question

잠시 동안 Ternary Search Tree을 사용하고 있었는데, 자동 완성 드롭 다운 콤보 상자를 구현하는 데이터 구조로 사용되었습니다. "FO"사용자 유형, 콤보 상자 드롭 다운이

foo는 음식 축구

문제는, 삼항 검색 나무의 사용 나의 현재를 표시 할 때 어떤는 대소 문자를 구분 의미한다. 내 구현은 다음과 같습니다. 그것은 약 1 + + 예를 들어 현실 세계에서 사용되었습니다. 따라서 나는 그것을 꽤 신뢰할 만하다고 생각한다.

My Ternary Search Tree code

그러나, 나는 의미를 구분하지 삼항 검색 트리, 나는 "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를 핵심 백본으로 사용하고 있습니다.

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

내 현재의 3 진 검색 트리가 대소 문자를 구분하지 않는 검색을 어렵게 만드는 핵심 요소 중 하나는 내 기본 데이터 구조가 일대일 매핑입니다. 다음 테스트 코드를보고하십시오 : 내 현재의 단기 솔루션은 내가 전체 TernarySearchTree을 마무리하는 TSTSearchEngine를 사용하고 있다는 것입니다

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은

(1) 맵핑에 대문자 키를 제공하는 TernarySearchTree로 구성됩니다.

(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을 배열 목록에 삽입하기 위해 map의 키로 사용합니다.

(3) name1.toString()은 대문자 ("ABC")로 변환됩니다. TernarySearchTree에 삽입됩니다. S1은 TernarySearchTree의 키와 값 모두입니다.

(4) "ABC"는 name1을 배열 목록에 삽입하기 위해 map의 키로 사용합니다.

나는 (1) TernarySearchTree는 "ABC"를 반환합니다

engine.searchAll("a"); 

하려고합니다.

(2) "ABC"가지도에 액세스하는 데 사용됩니다. Map은 name0과 name1이 포함 된 배열 목록을 반환합니다.

이 솔루션이 작동합니다. 샘플 코드는 Sample Code for New TSTSearchEngine

을 참조 할 수 있습니다. 그러나 두 번의 검색이 필요하므로이 방법은 효과적이지 않을 수 있습니다. 거기에 C에서 구현을 찾을 수 C++ Implementation of Case Insensitive Ternary Search Tree. 따라서 C++ 코드를 Java로 포팅 할 수있는 기회가 있습니다.

Answer 2

나는 전에 TST를 사용하지 않은, 그러나 이것은 보관시 및 조회시 모두 낮은 또는 키를 uppercasing만큼 간단하지 않다? 코드 스 니펫에서 작동해야하는 것처럼 보입니다.

Answer 3

나는 삼항 검색 트리를 구현했습니다, 당신은 사례 insensative의로 http://kunalekawde.blogspot.com/2010/05/radix-patricia-and-ternary.html 에 모습을 가질 수 중 하나 진수/DEC 값에 작은 모자를 매핑하거나 접두사를 가져 오는 동안, 값을 확인하십시오.