Java에서 간단한 접두사 색인을 만드는 방법은 무엇입니까?

Question

큰 세트의 URL이 있는데 자동 완성을 구현하고 싶습니다. 이 세트의 크기와 선형이기 때문에 나는 순진 접근 방식의 복잡성을 좋아하지 않는다 :

지금은 해시 세트에서, 함수가 O "의 작품"(을)를 포함 "알고

for(String url: urls) if(url.startsWith(input) {doSomething();} 

(1) "containsPrefix()"는 없습니다. Lucene과 같은 큰 라이브러리를 사용하거나 직접 코딩하지 않고도 간단한 방법이 있습니까? 문제가 없지만 간단한 문제가 너무 복잡해서 기존의 간단한 해결책이 있는지 알고 싶습니다. :-)

컴퓨터 과학 수업에서 문자열 조각으로 구성된 트리를 기억하지만 나는 그것이 어떻게 부르는지 잊는다. 그것은 다음과 같이 작동했습니다 :

[car, care, carrot,carrotville]-> 

car 
| 
-/ 
-e 
-rrot 
    | 
    ----ville 

P .: 나는 문자열이 접두사 인 모든 문자열을 반환하는 메소드를 어떻게 호출합니까? a가 b의 접두사 인 것처럼, b는 무엇입니까? 당신이 Trie, 그 목적을 위해 정밀하게 설계된 데이터 구조를 사용, 효율적으로 문자열의 접두사를 찾을 필요가

Answer 1

:

트라이, 또는 접두사 트리에 사용되는 명령 트리 데이터 구조입니다 키가 일반적으로 문자열 인 연관 배열을 저장합니다. 이진 검색 트리와 달리 트리의 아무 노드도 해당 노드와 연관된 키를 저장하지 않습니다. 대신 트리의 해당 위치는 키가 연결된 키를 정의합니다. 노드의 모든 후손은 해당 노드와 관련된 문자열의 공통 접두어가, 루트는 빈 문자열로 sampleimplementations와

두 링크가 연결되어 있습니다.

Answer 2

오래 전에 내가 여기에 간단한 트리는 구현을 넣어 :

http://code.google.com/p/triebag/source/browse/trunk/src/triebag/tries/SimpleTrie.java

그러나이 소형 트리는 아니다, 그래서 컴팩트 한 조금 까다 롭습니다 만들기, 캐릭터 당 하나 개의 노드를 작성합니다.

Answer 3

좋은 대안 너 한테은 ternary search tree (효율적인 메모리) 여기

https://github.com/varunpant/TernaryTree/tree/master/TernaryTree 자바에서 트라이입니다 http://algs4.cs.princeton.edu/52trie/TrieST.java.html

Answer 4

효율적으로 접두사 처리 할 수 ​​

정규 표현식 구현 있으며, java.util.regex.Pattern :

을

StringBuilder buffer = new StringBuilder(); 
for (String prefix : prefixes) { 
    if (buffer.length() > 0) 
     buffer.append("|"); 
    buffer.append(prefix); 
} 
Pattern prefixPattern = Pattern.compile("^(" + buffer + ")"); 

당신은 모든 접두사를 테스트 할 수 있습니다

boolean containsPrefix = prefixPattern.matcher(stringToTest).find(); 

참고 : 간단히 말하면 접두사 문자열은 이스케이프되지 않습니다. 정규 표현식 문자 [,], \, *,?, $, ^, (,), {,} 및 | \가 앞에 붙어야한다.