효율적인 대량 문자열 검색 문제

Question

문제점 : 큰 정적 정적 문자열 목록이 제공됩니다. 데이터와 와일드 카드 요소 (*와?)로 구성된 패턴 문자열. 아이디어는 패턴과 일치하는 모든 문자열을 반환하는 것입니다.

현재 솔루션 : 현재 큰 목록을 검색하고 각 항목을 패턴과 대조하는 선형 접근 방식을 사용하고 있습니다.

내 질문 : 검색의 복잡성이 O (n)보다 적도록 큰 목록을 저장할 수있는 적합한 데이터 구조가 있습니까?

아마도 접미사와 비슷한 무엇입니까? 나는 또한 해시 테이블에서 bi-tri-gram을 사용하는 방법을 고려해 보았지만 반환 된 단어 목록과 패턴의 병합을 기반으로 일치를 평가하는 데 필요한 논리는 악몽이며 올바른 것임을 확신하지 못합니다. 접근.

Answer 1

메모리를 신경 쓰지 않아도 목록을 사전 처리 할 수 ​​있으면 [ 'hello', 'world']와 같은 원래 단어를 가리키는 모든 접미사의 정렬 된 배열을 만듭니다. 이것을 저장하십시오 :

[('d' , 'world'), 
('ello' , 'hello'), 
('hello', 'hello'), 
('ld' , 'world'), 
('llo' , 'hello'), 
('lo' , 'hello'), 
('o' , 'hello'), 
('orld' , 'world'), 
('rld' , 'world'), 
('world', 'world')] 

이 배열을 사용하여 패턴 조각을 사용하여 후보 경기 세트를 작성하십시오.

예를 들어, 패턴이 *or* 인 경우 부분 문자열 or에서 이진 잘라 내기를 사용하여 일치 항목 ('orld' , 'world')을 찾은 다음 정상적인 globbing 방식을 사용하여 일치를 확인하십시오.

와일드 카드가 더 복잡한 경우 (예 : h*o) h 및 o에 대한 후보 집합을 만들고 최종 선형 glob 전에 교차 부분을 찾습니다.

Answer 2

일반 트라이를 만들고 와일드 카드 가장자리를 추가 할 수 있습니다. 당신의 복잡성은 O (n)입니다. 여기서 n은 패턴의 길이입니다. 패턴 0에서 **의 런을 *으로 바꿔야합니다 (또한 O (n) 작업 임).

단어의 목록이 있다면 나는 황소가 후 트라이 조금 같을 것이다 이니

 
    (I ($ [I]) 
    a (m ($ [am]) 
     n ($ [an]) 
     ? ($ [am an]) 
     * ($ [am an])) 
    o (x ($ [ox]) 
     ? ($ [ox]) 
     * ($ [ox])) 
    ? ($ [I] 
     m ($ [am]) 
     n ($ [an]) 
     x ($ [ox]) 
     ? ($ [am an ox]) 
     * ($ [I am an ox] 
     m ($ [am]) ...) 
    * ($ [I am an ox] 
     I ... 
    ... 

을 그리고 여기 샘플 파이썬 프로그램입니다 : 동의

 
import sys 

def addWord(root, word): 
    add(root, word, word, '') 

def add(root, word, tail, prev): 
    if tail == '': 
     addLeaf(root, word) 
    else: 
     head = tail[0] 
     tail2 = tail[1:] 
     add(addEdge(root, head), word, tail2, head) 
     add(addEdge(root, '?'), word, tail2, head) 
    if prev != '*': 
     for l in range(len(tail)+1): 
      add(addEdge(root, '*'), word, tail[l:], '*') 

def addEdge(root, char): 
    if not root.has_key(char): 
     root[char] = {} 
    return root[char] 

def addLeaf(root, word): 
    if not root.has_key('$'): 
     root['$'] = [] 
    leaf = root['$'] 
    if word not in leaf: 
     leaf.append(word) 

def findWord(root, pattern): 
    prev = '' 
    for p in pattern: 
     if p == '*' and prev == '*': 
      continue 
     prev = p 
     if not root.has_key(p): 
      return [] 
     root = root[p] 
    if not root.has_key('$'): 
     return [] 
    return root['$'] 

def run(): 
    print("Enter words, one per line terminate with a . on a line") 
    root = {} 
    while 1: 
     line = sys.stdin.readline()[:-1] 
     if line == '.': break 
     addWord(root, line) 
    print(repr(root)) 
    print("Now enter search patterns. Do not use multiple sequential '*'s") 
    while 1: 
     line = sys.stdin.readline()[:-1] 
     if line == '.': break 
     print(findWord(root, line)) 

run() 

Answer 3

가 접미어 트라이는 시도하기 좋은 아이디어입니다. 단, 데이터 세트의 크기가 크기 때문에 사용량만큼의 시간을 절약 할 수 있습니다. 건설 비용을 상각하기 위해 여러 번 쿼리해야한다면 가장 좋습니다. 아마 몇백 개의 쿼리.

또한 병렬 처리에 대한 좋은 설명입니다. 목록을 두 개로 잘라서 두 개의 서로 다른 프로세서에주고 작업을 두 배 빨리 수행하십시오.

Answer 4

현재 선형 검색을 수행 중이라고하셨습니다. 가장 자주 수행되는 쿼리 패턴에 대한 데이터를 제공합니까? 예 : blah*은 현재 사용자 중 bl?h (나는 그럴 것이라고 추정 함)보다 훨씬 일반적입니까?

이런 종류의 사전 지식을 사용하면 색인 생성 작업을 일반적인 경우에 집중하여 O (1)로 가져올 수 있습니다. 훨씬 어렵고 훨씬 덜 가치있는 문제를 해결하는 대신 모든 가능한 검색어가 똑같이 빠릅니다.

Answer 5

문자열의 문자 수를 유지함으로써 간단한 속도 향상을 얻을 수 있습니다. b이 없거나 하나만 b 인 문자열은 쿼리 abba*과 일치 할 수 없으므로 테스트 할 필요가 없습니다. 당신의 끈이 그것들로 만들어 졌다면 이것은 문자보다 더 많은 단어가 있기 때문에 전체 단어에서 훨씬 잘 작동합니다; 게다가 인덱스를 만들 수있는 많은 라이브러리가 있습니다. 반면에, 그것은 당신이 언급 한 n-gram 접근법과 매우 유사합니다.

라이브러리를 사용하지 않는 경우 색인에서 가장 자주 사용되지 않는 문자 (또는 단어 또는 n 그램)를 먼저 찾아보고 쿼리를 최적화 할 수 있습니다. 이렇게하면 더 일치하지 않는 문자열을 앞에 버릴 수 있습니다.

일반적으로 모든 속도 향상은 일치하지 않는 항목을 삭제한다는 아이디어를 기반으로합니다. 색인을 생성하는 대상 및 방법은 데이터에 따라 다릅니다. 예를 들어, 일반적인 패턴 길이가 문자열 길이에 가까우면 문자열이 패턴을 보유 할 수있을만큼 충분히 긴지를 확인하기 만하면됩니다.

Answer 6

다중 문자열 검색에는 많은 알고리즘이 있습니다. Google "Navarro 문자열 검색"을 사용하면 여러 문자열 옵션을 효과적으로 분석 할 수 있습니다. 많은 알고리즘은 "보통"의 경우 (검색 문자열이 상당히 길다 : Wu-Manber, 검색 대상 텍스트에서 알 수없는 희귀 한 문자로 구성된 검색 문자열 : 병렬 Horspool)에 매우 적합합니다. Aho-Corasick은 검색에서 최악의 행동을 만들기 위해 입력 텍스트를 조정하는 방법에 관계없이 입력 문자 당 제한된 양의 작업을 보장하는 알고리즘입니다. Snort와 같은 프로그램의 경우 DoS (서비스 거부) 공격에 매우 중요합니다. Aho-Corasick 검색을 효과적으로 구현하는 방법에 관심이 있으시면 ACISM - an Aho-Corasick Interleaved State Matrix을 살펴보십시오.