으로 문자열 검색. 와일드 카드

Question

배열이 너무 많아서 패턴을 검색하려고합니다. 이 패턴에는 "." 각 (각) 1 문자 (모두)와 일치하는 와일드 카드. 예를 들어

는 :

myset = {"bar", "foo", "cya", "test"} 

find(myset, "f.o") -> returns true (matches with "foo") 
find(myset, "foo.") -> returns false 
find(myset, ".e.t") -> returns true (matches with "test") 
find(myset, "cya") -> returns true (matches with "cya") 

나는 myset 실제로 매우 큰 배열 때문에 빨리이 알고리즘을 구현하는 방법을 찾기 위해 노력했지만 내 아이디어 중 어느 것도

(예를 O(size_of(myset) * lenght(pattern))에 대한) 충분한 복잡성이 없습니다

편집 :

myset은 거대한 배열이므로 단어가 크지 않습니다. 나는 천천히 전처리 할 수있다. 하지만 find() 쿼리가 너무 많으므로 find() 나는 가능한 한 빨리 find()을 원합니다.

Answer 1

당신은 당신의 세트에있는 모든 단어의 코퍼스의 접미사 트리를 만들 수이 데이터 구조를 사용하여 (see this link) 은 복잡 n은 인 트리를 구축하기 위해 (n)이 O의 1 시간 비용을 포함 할 것 모든 단어의 길이의 합계.

일단 트리가 작성되면 문자열이 일치하는지 찾는 작업은 O (n) 만 받아야합니다. 여기서 n은 문자열의 길이입니다.

Answer 2

세트가 고정되어있는 경우 문자 c이 위치 p에있는 것으로 미리 계산할 수 있습니다 (가치가 있다고 생각되는만큼 p 값만큼). 그런 다음 각 요소 테스트 문자에 대해 배열을 한 번 검색합니다 귀하가 가장 일찍 퇴장 할 가능성이있는 순서의 특정 위치에 있습니다.

Answer 3

먼저 단어 길이 당 집합으로 자료를 나눕니다. find()에 대한 입력은 항상 특정 길이의 일치가 필요하기 때문에 찾기 알고리즘은 적절한 세트를 검색 할 수 있으며 알고리즘은 동일한 길이의 모든 단어와 잘 작동하도록 설계 할 수 있습니다.

다음 (각 집합에 대해) 문자 x 위치의 해시와 일치하는 단어 목록의 해시지도를 만듭니다. 많은 양의 해시 충돌이있는 것이 좋습니다. 델타 및 런 - 길이 인코딩을 사용하여 일치하는 단어 목록의 크기를 줄일 수 있습니다.

검색하려면 검색 입력 길이에 적합한 해시 맵을 선택하고 각각의 . 문자가 아닌 경우 해당 문자 x 위치의 해시를 계산하고 AND 단어 목록을 함께 사용하면 훨씬 줄어든 목록을 얻을 수 있습니다.

매우 작은 목록을 통해 무작위 검색.

Answer 4

집합에있는 단어의 길이가 길지 않은 것이 확실하다면. 두 번째 문자가 단어의 'A', 'B'의 첫 번째 문자가 단어의 목록 ..

목록의 첫 번째 문자가 단어의

목록 : 당신은 아마 다음을 보유하고 테이블을 만들 수 있습니다 'a', 두 번째 문자 'b'가있는 단어 목록 ..

등등.

단어를 검색 할 때.검색 문자열의 첫 번째 문자와 첫 번째 문자가 같은 단어 목록을 찾을 수 있습니다. 이 세련된 목록을 사용하여 두 번째 문자가 검색 문자열의 두 번째 문자와 같은 단어를 찾습니다. '무시할 수 있습니다.' 당신이 그들을 만날 때마다.

테이블을 만드는 데 많은 공간이 필요할 수 있지만 시간이 많이 걸릴 것으로 알고 있습니다. 당신이 = { "바", "foo는", "CYA", "테스트"} 요소인지하고 당신이

순간 '구경에게'를 검색 할 경우

는 예를 들어, 시작하는 단어의 목록을 확인 f를 사용하면 나머지 세트를 제거합니다. 그냥 아이디어 .. 희망이 도움이됩니다.

Answer 5

나는이 같은 질문을했으며 인터넷에서 발견 한 대부분의 아이디어/솔루션에 완전히 만족하지 않았습니다. 제 생각에는 "올바른"방법은 Directed Acyclic Word Graph을 사용하는 것입니다. 나는 그렇게하지 못했지만 유사한 효과를 얻으려면 Trie에 추가 논리를 추가했습니다.

find() 인터페이스와 유사하게 구현 된 내 isWord()을 참조하십시오. Trie를 되풀이하고 와일드 카드로 분기 한 다음 결과를 공통 집합으로 다시 수집하여 작동합니다. (findNodes()을 참조하십시오.)

getMatchingWords()은 쿼리가 어떤 것과도 일치하는지 여부에 대한 부울 대신 일치하는 단어 집합을 반환한다는 점을 제외하고는 정신이 비슷합니다.