맞 춤 법 검사 의 네 가지 실현

알고리즘 이 재 미 있 는 점 은 같은 문 제 를 다른 방식 으로 처리 할 수 있 고 더 좋 은 방법 이 있다 는 점 이다.맞 춤 법 검사 같은 거.
맞 춤 법 검 사 는 대체로 이렇다. 사전 파일 을 제시 하고 비교 파일 을 제시한다.파일 에 있 는 단어 보다 사전 파일 에 단어 가 없 으 면 맞 춤 법 이 틀 렸 다 고 생각 합 니 다.파일 에 있 는 모든 맞 춤 법 보다 잘못된 단 어 를 찾 는 것 이 중요 하 다.
폭력 해체 (brute force)
가장 직관 적 인 방법 은 파일 에 있 는 단 어 를 사전 에 있 는 단어 와 비교 하고 사전 에 없 으 면 출력 한다.가장 간단 하고 시간 도 많이 걸린다.
사전 파일 에 모두 nd 문자 가 있다 고 가정 하면 비교 할 파일 에 nt 문자 가 있 고 복잡 도 는 O (nd * nt) 입 니 다.
구체 적 실현
실행 속 도 를 살 펴 보 자. 테스트 용 사전 에는 약 14 만 개의 단어 가 있 는데, 비교 파일 에는 약 12 만 개의 단어 가 있다.3 분 가까이 걸 립 니 다.분명히 속도 가 너무 느 려 서 최적화 가 필요 하 다.
단어 찾기 트 리 (Trie)
우 리 는 주어진 단어 가 a 로 시작 하면 사전에 서 다른 자모 로 시작 하 는 단 어 는 우리 가 비교 할 필요 가 없다 는 것 을 안다.이 진 트 리 를 찾 는 것 과 같 습 니 다. 찾 을 때마다 요구 에 부합 되 지 않 는 반 을 버 릴 수 있 습 니 다.이 진 트 리 의 깨 우 침 을 받 아 우 리 는 트 리 라 는 다 진 트 리 를 사용 하여 실현 할 수 있다.
사전 에 ab, ac, c, d 라 는 네 단어 가 있다 고 가정 하면 생 성 된 trie 는 다음 과 같은 모양 일 것 이다 (t1, t2 는 표현 일 뿐 토론 하기에 편리 하 다).

   root(t1)
  /    \     \
 a(t2)  c(t3) d(t4)
/     \
b(t5)  c(t6)

검 사 를 할 때 는 노드 와 한 단계 한 단계 아래로 찾 아야 한다.만약 에 우리 가 'ad' 를 찾는다 고 가정 하면 뿌리 노드 의 하위 노드 t2 의 값 은 a 이 고 첫 번 째 자모 가 일치 하 는 데 성공 했다.두 번 째 바이트 'd', t2 의 하위 트 리 에 'd' 라 는 글자 가 없습니다. 일치 하 는 데 실 패 했 습 니 다."ad" 는 잘못된 맞 춤 법 입 니 다.우리 가 단어의 모든 자모 와 일치 하고 마지막 자모 가 끝 자모 일 때 만 이 단 어 는 사전에 존재 한다.
구체 적 실현
같은 입력 을 사용 하 는 데 1.3 초 밖 에 걸 리 지 않 아 수백 배 나 빨 랐 다.
해시 표 (해시 표)
맞 춤 법 찾기 는 삽입 과 검색 속도 가 빠 르 고 Hash Table 이 요구 에 부합 합 니 다.같은 데 이 터 는 0.14 초 만 에 trie 의 실현 보다 10 배 가까이 빨 랐 다.구체 적 실현
Bloom Filter
Hash Table 은 속도 적 으로 한계 가 있어 가장 적합 한 알고리즘 으로 보 입 니 다.하지만 Bloom Filter 는 어느 정도 잘 어 울 려 요!
Bloom Filter 는 Hash Table 에 비해 가장 큰 장점 은 Bloom Filter 가 완전한 key (예 를 들 어 단어) 를 저장 하지 않 아 도 된다 는 것 이다.Bloom Filter 는 키 (예 를 들 어 단어) 를 여러 개의 해시 방정식 을 통 해 한 배열 에 투사 하고 이 배열 에 따라 이 단어 가 삽입 되 었 는 지 여 부 를 판단 할 수 있 습 니 다.
알고리즘 의 대체 적 인 사 고 는 다음 과 같다. n 개의 bit 배열 arr 를 초기 화하 고 특정한 값 을 삽입 할 때 우 리 는 해시 방정식 을 통 해 해당 하 는 index 를 얻 고 배열 의 이 위 치 를 1 로 설정 합 니 다. 만약 에 우리 가 2 개의 해시 방정식 h1, h2 를 사용한다 고 가정 하면 우 리 는 두 개의 index (1 개 일 수 있 습 니 다) 를 얻 을 수 있 습 니 다. 우 리 는 배열 의 이 두 위 치 를 1 로 설정 합 니 다.
찾 을 때 모든 해시 방정식 을 사용 하여 해당 하 는 index 를 얻 은 다음 배열 이 이 위치 에 있 는 지, 모두 1 인지, 모두 1 이면 이 값 이 삽입 되 었 다 고 생각 합 니 다.
의사 코드 는 다음 과 같 습 니 다:

require 'bitarray'
class BloomFilter
  attr_accessor :arr
  def initialize
    self.arr = BitArray.new(n)
  end

  def insert(key)
    arr[h1(key)] = 1
    arr[h2(key)] = 1
  end

  def include?(key)
    arr[h1(key)] == 1 && arr[h2(key)] = 1
  end

  # BloomFilter        ，2              。
  def h1(key)
    # xxx
  end

  def h2(key)
    # xxx
  end
end

Bloom Filter 는 공간 을 크게 절약 하 였 으 나 어느 정도 오류 가 발생 할 확률 이 있 습 니 다 (false positive). 이 오 류 는 찾 을 때 한 값 이 삽입 되 지 않 았 으 나 삽입 되 었 다 고 오 해 를 받 았 습 니 다.해시 방정식 이 충돌 하기 때문이다.
더 긴 배열 과 더 많은 해시 방정식 을 통 해 이 문 제 를 해결 할 수 있 고 동료 공간 도 실 용적 이지 않 기 때문에 유용 한 알고리즘 이다.
Bloom Filter 는 삭제 작업 을 할 수 없다 는 단점 도 있다.하지만 모든 사람 에 게 counter 를 붙 여 해결 할 수 있 습 니 다. 이른바 Counting Bloom Filter 입 니 다. 이 글 을 구체 적 으로 보면 상세 하지 않 습 니 다.
구체 적 실현
같은 입력 은 0.11 초 걸 립 니 다.
실행 속도 대비

SpellChecker
                      user     system      total        real
brute_force     162.660000   1.560000 164.220000 (168.961906)
by_trie           1.160000   0.100000   1.260000 (  1.305419)
by_hash_table     0.140000   0.000000   0.140000 (  0.145828)
by_bloom_filter   0.100000   0.010000   0.110000 (  0.108583)

관련 코드
레 퍼 런 스
Problem Set 5: MispellingsBloom Filters: Heuristic AnalysisBloom Filter 개념 과 원리 A Look Into Bloom Filters with Ruby