누락 된 문자가있는 단어를 찾기위한 좋은 알고리즘 및 데이터 구조?
그래서 사전에서 누락 된 문자가있는 단어를 찾는 효율적인 알고리즘을 작성해야하고 가능한 단어 세트를 원합니다.
예를 들어, 내가 th ?? e를 가지고 있다면, 나는 이것들, 그것들, 테마, there.etc를 돌려받을 수 있습니다.
누군가 내가 사용해야하는 데이터 구조 나 알고리즘을 제안 할 수 있는지 궁금합니다.
감사!
편집 : Trie는 공간이 너무 비효율적이며 너무 느려질 것입니다. 다른 아이디어 수정이 있습니까?
업데이트 : 최대 두 개의 물음표가 있으며 두 개의 물음표가 발생하면 순서대로 발생합니다.
현재 정확히 일치하는 경우 3 개의 해시 테이블, 1 개의 물음표 및 2 개의 물음표를 사용하고 있습니다. 사전이 주어지면 가능한 모든 단어를 해시합니다. 예를 들어, WORD라는 단어가있는 경우. 나는 WORD,? ORD, W? RD, WO? D, WOR ?, ?? RD, W ?? D, WO ??를 해시합니다. 사전에. 그런 다음 링크 목록을 사용하여 충돌을 함께 연결합니다. 따라서 hash (W? RD) = hash (STR? NG) = 17이라고 말하십시오. hashtab (17)은 연결 목록이기 때문에 WORD를 가리키고 WORD는 STRING을 가리 킵니다.
한 단어의 평균 조회 시간은 약 2e-6s입니다. 나는 더 나은 일을 찾고 있는데, 바람직하게는 1e-9 정도입니다.
편집 :이 문제를 다시 보지 않았지만 3m 항목 삽입에는 0.5 초가 걸렸고 3m 항목 조회에는 4 초가 걸렸습니다.
감사!
이 경우 각 단어가 한 줄에있는 플랫 파일을 사용하는 것이 가장 좋습니다. 이를 통해 고도로 최적화 된 정규식 검색 기능을 편리하게 사용할 수 있으며이 문제에 대해 스스로 고안 할 수있는 모든 데이터 구조를 능가 할 것입니다.
솔루션 # 1 : Regex 사용
이 문제에 대한 Ruby 코드가 작동합니다.
def query(str, data)
r = Regexp.new("^#{str.gsub("?", ".")}$")
idx = 0
begin
idx = data.index(r, idx)
if idx
yield data[idx, str.size]
idx += str.size + 1
end
end while idx
end
start_time = Time.now
query("?r?te", File.read("wordlist.txt")) do |w|
puts w
end
puts Time.now - start_time
파일 wordlist.txt에는 45425 단어가 포함되어 있습니다 ( 여기에서 다운로드 가능 ). 쿼리 ?r?te에 대한 프로그램의 출력은 다음 과 같습니다.
brute
crate
Crete
grate
irate
prate
write
wrote
0.013689
따라서 전체 파일을 읽고 모든 일치 항목을 찾는 데 37 밀리 초 만 걸립니다. 그리고 Trie가 매우 느린 경우에도 모든 종류의 쿼리 패턴에 대해 매우 잘 확장됩니다.
질문 ????????????????e
counterproductive
indistinguishable
microarchitecture
microprogrammable
0.018681
질문 ?h?a?r?c?l?
theatricals
0.013608
이것은 나를 위해 충분히 빠르다.
솔루션 # 2 : 준비된 데이터가있는 정규식
더 빨리 가고 싶다면 단어 목록을 같은 길이의 단어가 포함 된 문자열로 분할하고 쿼리 길이에 따라 올바른 단어를 검색 할 수 있습니다. 마지막 5 줄을 다음 코드로 바꿉니다.
def query_split(str, data)
query(str, data[str.length]) do |w|
yield w
end
end
# prepare data
data = Hash.new("")
File.read("wordlist.txt").each_line do |w|
data[w.length-1] += w
end
# use prepared data for query
start_time = Time.now
query_split("?r?te", data) do |w|
puts w
end
puts Time.now - start_time
이제 데이터 구조를 작성하는 데 약 0.4 초가 걸리지 만 모든 쿼리가 약 10 배 더 빠릅니다 (해당 길이의 단어 수에 따라 다름).
?r?te0.001112 초?h?a?r?c?l?0.000852 초????????????????e0.000169 초
솔루션 # 3 : 하나의 Big Hashtable (업데이트 된 요구 사항)
요구 사항을 변경 했으므로 미리 계산 된 모든 결과를 포함하는 하나의 큰 해시 테이블 만 사용하도록 아이디어를 쉽게 확장 할 수 있습니다. 그러나 충돌을 직접 해결하는 대신 올바르게 구현 된 해시 테이블의 성능에 의존 할 수 있습니다.
여기에서 가능한 각 쿼리가 결과 목록에 매핑되는 하나의 큰 해시 테이블을 만듭니다.
def create_big_hash(data)
h = Hash.new do |h,k|
h[k] = Array.new
end
data.each_line do |l|
w = l.strip
# add all words with one ?
w.length.times do |i|
q = String.new(w)
q[i] = "?"
h[q].push w
end
# add all words with two ??
(w.length-1).times do |i|
q = String.new(w)
q[i, 2] = "??"
h[q].push w
end
end
h
end
# prepare data
t = Time.new
h = create_big_hash(File.read("wordlist.txt"))
puts "#{Time.new - t} sec preparing data\n#{h.size} entries in big hash"
# use prepared data for query
t = Time.new
h["?ood"].each do |w|
puts w
end
puts (Time.new - t)
출력은
4.960255 sec preparing data
616745 entries in big hash
food
good
hood
mood
wood
2.0e-05
쿼리 성능은 O (1)이며 해시 테이블의 조회 일뿐입니다. 2.0e-05 시간은 아마도 타이머의 정밀도보다 낮을 것입니다. 1000 번 실행하면 쿼리 당 평균 1.958e-6 초를 얻습니다. 더 빨리 얻기 위해 C ++로 전환하고 메모리 효율성이 뛰어나고 빠른 Google Sparse Hash 를 사용합니다 .
솔루션 # 4 : 진지 해지십시오
위의 모든 솔루션이 작동하며 많은 사용 사례에 충분해야합니다. 정말로 진지 해지고 싶고 손에 많은 여가 시간이 있다면 좋은 논문을 읽으십시오.
- 대략적인 문자열 일치 시도 -잘 구현 된 경우 시도는 매우 작은 메모리 요구 사항 (사전 자체보다 50 % 적은 공간)을 가질 수 있으며 매우 빠릅니다.
- Agrep-빠른 근사 패턴 일치 도구 -Agrep은 근사 문자열 일치를위한 새롭고 효율적이고 유연한 알고리즘을 기반으로합니다.
- 대략적인 문자열 일치를위한 Google 학술 검색 검색 -이 주제에 대해 읽기에 충분합니다.
현재 제한 사항을 고려할 때 :
- 최대 2 개의 물음표가 있습니다.
- 두 개의 물음표가 있으면 함께 나타납니다.
- 사전에는 ~ 100,000 개의 단어가 있으며 평균 단어 길이는 6입니다.
두 가지 실행 가능한 솔루션이 있습니다.
빠른 솔루션 : HASH
최대 2 개의 '?'와 함께 단어가되는 해시를 사용할 수 있으며 값은 적합한 단어 목록입니다. 이 해시에는 약 100,000 + 100,000 * 6 + 100,000 * 5 = 1,200,000 개의 항목이 있습니다 (물음표 2 개가있는 경우 첫 번째 물음표의 위치를 찾아야합니다 ...). 각 항목은 단어 목록 또는 기존 단어에 대한 포인터 목록을 저장할 수 있습니다. 포인터 목록을 저장하고 두 개의 '?'가있는 각 단어와 일치하는 단어가 평균 20 개 미만이라고 가정하면 추가 메모리는 20 * 1,200,000 = 24,000,000 미만입니다.
각 포인터 크기가 4 바이트 인 경우 여기에 필요한 메모리는 (24,000,000 + 1,200,000) * 4 바이트 = 100,800,000 바이트 ~ = 96 메가 바이트입니다.
이 솔루션을 요약하려면 :
- 메모리 소비 : ~ 96MB
- 각 검색 시간 : 해시 함수를 계산하고 포인터를 따라갑니다. O (1)
참고 : 더 작은 크기의 해시를 사용하려는 경우 가능하지만 성능 향상을 위해 연결 목록 대신 각 항목에 균형 검색 트리를 저장하는 것이 좋습니다.
공간에 정통하지만 여전히 매우 빠른 솔루션 : TRIE 변형
이 솔루션은 다음 관찰을 사용합니다.
'?' 기호는 단어의 끝에 있었고 trie는 훌륭한 솔루션이 될 것입니다.
trie의 검색은 단어의 길이로 검색하고 마지막 두 글자의 경우 DFS 순회는 모든 엔딩을 가져옵니다. 매우 빠르고 메모리에 정통한 솔루션입니다.
따라서이 관찰을 사용하여 정확히 이와 같이 작동하는 무언가를 구축해 보겠습니다.
사전에있는 모든 단어를 @ (또는 사전에없는 다른 기호)로 끝나는 단어로 생각할 수 있습니다. 따라서 'space'라는 단어는 'space @'가됩니다. 이제 각 단어를 '@'기호로 회전하면 다음과 같은 결과가 나타납니다.
space@, pace@s, ace@sp, *ce@spa*, e@spac
(첫 글자로 @ 없음).
이러한 변형을 모두 TRIE에 삽입하면 단어를 '회전'하여 단어 길이에서 원하는 단어를 쉽게 찾을 수 있습니다.
예 : 's ?? ce'에 맞는 모든 단어를 찾으려고합니다 (하나는 공백이고 다른 하나는 슬라이스입니다). s ?? ce @라는 단어를 작성하고? 기호는 끝에 있습니다. 즉 'ce @ s ??'
모든 회전 변형은 trie 내부에 존재하며 특히 'ce @ spa'(위에 *로 표시됨)가 있습니다. 시작이 발견되면 적절한 길이의 모든 연속을 검토하고 저장해야합니다. 그런 다음 @가 마지막 문자가되도록 다시 회전해야하고 walla-찾고 있던 모든 단어가 있습니다!
이 솔루션을 요약하려면 :
메모리 소비 : 각 단어에 대해 모든 회전이 트라이에 나타납니다. 평균적으로 메모리 크기의 * 6이 트라이에 저장됩니다. 트라이 크기는 내부에 저장된 공간의 약 * 3 (추측 ...)입니다. 따라서이 트라이에 필요한 총 공간은 6 * 3 * 100,000 = 1,800,000 단어 ~ = 6.8 메가 바이트입니다.
각 검색 시간 :
- 단어 회전 : O (단어 길이)
- trie에서 시작을 추구 : O (단어 길이)
- 모든 엔딩을 넘어서 : O (일치 수)
- 엔딩 회전 : O (전체 답변 길이)
요약하면, 매우 빠르며 단어 길이 * 작은 상수에 따라 다릅니다.
요약하자면 ...
두 번째 선택은 시간 / 공간이 매우 복잡하며 사용하기에 가장 좋은 옵션입니다. 두 번째 솔루션에는 몇 가지 문제가 있습니다 (이 경우 첫 번째 솔루션을 사용하는 것이 좋습니다).
- 구현하기가 더 복잡합니다. 기본적으로 시도가 내장 된 프로그래밍 언어가 있는지 확실하지 않습니다. 없는 경우-직접 구현해야 함을 의미합니다.
- 잘 확장되지 않습니다. 내일 물음표를 단어 전체에 퍼뜨려 야하고 꼭 함께 결합 할 필요는 없다고 결정한다면, 두 번째 해결책을 어떻게 맞출 지 고민해야합니다. 첫 번째 솔루션의 경우 일반화하기가 매우 쉽습니다.
나에게이 문제는 Trie 데이터 구조에 적합한 것처럼 들립니다 . 트라이에 전체 사전을 입력 한 다음 단어를 찾습니다. 누락 된 문자의 경우 모든 하위 시도를 시도해야하는데, 이는 재귀 접근 방식으로 비교적 쉽게 수행 할 수 있습니다.
편집 : 나는 방금 Ruby에서 이것을 간단하게 구현했습니다 : http://gist.github.com/262667 .
Directed Acyclic Word Graph 는이 문제에 대한 완벽한 데이터 구조입니다. 트라이의 효율성을 결합하지만 (트라이는 DAWG의 특별한 경우로 볼 수 있음) 훨씬 더 공간 효율적입니다. 일반적인 DAWG는 단어가있는 일반 텍스트 파일 크기의 일부를 차지합니다.
특정 조건을 충족하는 단어를 열거하는 것은 간단하고 trie에서와 동일합니다. 깊이 우선 방식으로 그래프를 탐색해야합니다.
Anna의 두 번째 해결책은 이것에 대한 영감입니다.
먼저 모든 단어를 메모리에로드하고 사전을 단어 길이에 따라 섹션으로 나눕니다.
각 길이 에 대해 단어에 대한 포인터 배열의 n 복사본을 만듭니다 . 특정 문자 수만큼 회전 할 때 문자열이 순서대로 나타나도록 각 배열을 정렬합니다 . 예를 들어, 5 자 단어의 원래 목록이 [plane, apple, space, train, happy, stack, hacks]라고 가정합니다. 그러면 포인터의 5 개 배열은 다음과 같습니다.
rotated by 0 letters: [apple, hacks, happy, plane, space, stack, train]
rotated by 1 letter: [hacks, happy, plane, space, apple, train, stack]
rotated by 2 letters: [space, stack, train, plane, hacks, apple, happy]
rotated by 3 letters: [space, stack, train, hacks, apple, plane, happy]
rotated by 4 letters: [apple, plane, space, stack, train, hacks, happy]
(포인터 대신 단어를 식별하는 정수를 사용하면 플랫폼 공간이 절약됩니다.)
검색하려면 물음표가 끝에 나타나도록 패턴을 얼마나 회전해야하는지 물어보십시오 . 그런 다음 적절한 목록에서 이진 검색을 할 수 있습니다.
"ppy"와 일치하는 항목을 찾으려면 ppy를 만들기 위해 2만큼 회전해야합니다. 따라서 두 글자로 회전했을 때 순서대로 배열을 살펴보십시오. 빠른 이진 검색은 "happy"가 유일한 일치 항목임을 찾습니다.
th ?? g와 일치하는 것을 찾아야한다면 gth ??를 만들기 위해 4만큼 회전해야합니다. 따라서 이진 검색에서 일치하는 항목이 없음을 찾은 배열 4를 살펴보십시오.
이것은 물음표가 모두 함께 나타나는 한 얼마나 많은 물음표가 있는지에 관계없이 작동합니다.
사전 자체에 추가로 필요한 공간 : 길이가 N 인 단어의 경우 (길이가 N 인 단어 수의 N 배) 포인터 또는 정수를위한 공간이 필요합니다.
조회 당 시간 : O (log n) 여기서 n은 적절한 길이의 단어 수입니다.
Python으로 구현 :
import bisect
class Matcher:
def __init__(self, words):
# Sort the words into bins by length.
bins = []
for w in words:
while len(bins) <= len(w):
bins.append([])
bins[len(w)].append(w)
# Make n copies of each list, sorted by rotations.
for n in range(len(bins)):
bins[n] = [sorted(bins[n], key=lambda w: w[i:]+w[:i]) for i in range(n)]
self.bins = bins
def find(self, pattern):
bins = self.bins
if len(pattern) >= len(bins):
return []
# Figure out which array to search.
r = (pattern.rindex('?') + 1) % len(pattern)
rpat = (pattern[r:] + pattern[:r]).rstrip('?')
if '?' in rpat:
raise ValueError("non-adjacent wildcards in pattern: " + repr(pattern))
a = bins[len(pattern)][r]
# Binary-search the array.
class RotatedArray:
def __len__(self):
return len(a)
def __getitem__(self, i):
word = a[i]
return word[r:] + word[:r]
ra = RotatedArray()
start = bisect.bisect(ra, rpat)
stop = bisect.bisect(ra, rpat[:-1] + chr(ord(rpat[-1]) + 1))
# Return the matches.
return a[start:stop]
words = open('/usr/share/dict/words', 'r').read().split()
print "Building matcher..."
m = Matcher(words) # takes 1-2 seconds, for me
print "Done."
print m.find("st??k")
print m.find("ov???low")
내 컴퓨터에서 시스템 사전은 909KB이고이 프로그램은 단어를 저장하는 데 필요한 것 외에 약 3.2MB의 메모리를 사용합니다 (포인터는 4 바이트). 미만이 개 있기 때문에이 사전의 경우, 포인터 대신 2 바이트 정수를 사용하여 반으로 그것을 잘라 수 16 각 길이의 단어.
측정 : 내 컴퓨터 m.find("st??k")에서 0.000032 초, m.find("ov???low")0.000034 초 및 m.find("????????????????e")0.000023 초 내에 실행됩니다.
라이브러리 class RotatedArray와 bisect라이브러리 를 사용하는 대신 이진 검색을 작성하여 처음 두 숫자를 0.000016 초로 줄였습니다. 두 배 빠른 속도입니다. 이것을 C ++로 구현하면 더 빨라질 것입니다.
먼저 쿼리 문자열을 주어진 항목과 비교하는 방법이 필요합니다. 정규식을 사용하는 함수를 가정 해 봅시다 : matches(query,trialstr).
O (n) 알고리즘은 단순히 모든 목록 항목 (사전은 프로그램에서 목록으로 표시됨)을 통해 실행하여 각 항목을 쿼리 문자열과 비교하는 것입니다.
약간의 사전 계산을 통해 각 문자에 대한 추가 단어 목록을 작성하여 많은 쿼리에 대해이를 개선 할 수 있으므로 사전이 다음과 같이 보일 수 있습니다.
wordsbyletter = { 'a' : ['aardvark', 'abacus', ... ],
'b' : ['bat', 'bar', ...],
.... }
그러나 이것은 특히 쿼리 문자열이 알 수없는 문자로 시작하는 경우 제한적으로 사용됩니다. 따라서 주어진 단어에서 특정 문자가있는 위치에 주목하여 다음을 생성하여 더 잘할 수 있습니다.
wordsmap = { 'a':{ 0:['aardvark', 'abacus'],
1:['bat','bar']
2:['abacus']},
'b':{ 0:['bat','bar'],
1:['abacus']},
....
}
보시다시피, 인덱스를 사용하지 않으면 필요한 저장 공간의 양이 크게 증가합니다. 특히 n 단어와 평균 길이 m의 사전에는 nm 2 의 저장 공간 이 필요합니다 . 그러나 이제 매우 빠르게 검색하여 각 세트에서 일치 할 수있는 모든 단어를 얻을 수 있습니다.
최종 최적화 (순진한 접근 방식으로 사용할 수 있음)는 동일한 길이의 모든 단어를 별도의 저장소로 분리하는 것입니다. 단어의 길이를 항상 알고 있기 때문입니다.
이 버전은 O ( kx )입니다. 여기서 k 는 쿼리 단어 의 알려진 문자 수 이고 x = x ( n )은 구현에서 길이가 n 인 사전에서 단일 항목을 찾는 시간입니다 (일반적으로 log ( n ).
따라서 다음과 같은 최종 사전을 사용하십시오.
allmap = {
3 : {
'a' : {
1 : ['ant','all'],
2 : ['bar','pat']
}
'b' : {
1 : ['bar','boy'],
...
}
4 : {
'a' : {
1 : ['ante'],
....
그런 다음 알고리즘은 다음과 같습니다.
possiblewords = set()
firsttime = True
wordlen = len(query)
for idx,letter in enumerate(query):
if(letter is not '?'):
matchesthisletter = set(allmap[wordlen][letter][idx])
if firsttime:
possiblewords = matchesthisletter
else:
possiblewords &= matchesthisletter
마지막에 세트 possiblewords에는 일치하는 모든 문자가 포함됩니다.
패턴 (arate, arbte, arcte ... zryte, zrzte)과 일치하는 가능한 모든 단어를 생성 한 다음 사전의 이진 트리 표현에서 검색하면 평균 성능 특성은 O (e ^)입니다. N1 * log (N2)) 여기서 N1은 물음표의 수이고 N2는 사전의 크기입니다. 나에게 충분 해 보이지만 더 나은 알고리즘을 찾는 것이 가능하다고 확신합니다.
편집 : 세 개 이상의 물음표가 있으면 Phil H의 대답과 그의 편지 색인 방식을 살펴보십시오.
충분한 메모리가 있다고 가정하면 일정한 시간에 답을 제공하는 거대한 해시 맵을 만들 수 있습니다. 다음은 Python의 간단한 예입니다.
from array import array
all_words = open("english-words").read().split()
big_map = {}
def populate_map(word):
for i in range(pow(2, len(word))):
bin = _bin(i, len(word))
candidate = array('c', word)
for j in range(len(word)):
if bin[j] == "1":
candidate[j] = "?"
if candidate.tostring() in big_map:
big_map[candidate.tostring()].add(word)
else:
big_map[candidate.tostring()] = set([word])
def _bin(x, width):
return ''.join(str((x>>i)&1) for i in xrange(width-1,-1,-1))
def run():
for word in all_words:
populate_map(word)
run()
>>> big_map["y??r"]
set(['your', 'year'])
>>> big_map["yo?r"]
set(['your'])
>>> big_map["?o?r"]
set(['four', 'poor', 'door', 'your', 'hour'])
aspell 에서 어떻게 수행되는지 볼 수 있습니다 . 철자가 틀린 단어에 대해 올바른 단어를 제안합니다.
모든 단어의 해시 세트를 작성하십시오. 일치하는 항목을 찾으려면 패턴의 물음표를 가능한 각 문자 조합으로 바꾸십시오. 두 개의 물음표가있는 경우 쿼리는 26 2 = 676의 빠른 예상 시간 해시 테이블 조회로 구성됩니다.
import itertools
words = set(open("/usr/share/dict/words").read().split())
def query(pattern):
i = pattern.index('?')
j = pattern.rindex('?') + 1
for combo in itertools.product('abcdefghijklmnopqrstuvwxyz', repeat=j-i):
attempt = pattern[:i] + ''.join(combo) + pattern[j:]
if attempt in words:
print attempt
이것은 내 다른 대답보다 적은 메모리를 사용하지만 물음표를 더 추가하면 기하 급수적으로 느려집니다.
80-90 %의 정확도가 허용되는 경우 Peter Norvig의 맞춤법 검사기로 관리 할 수 있습니다. 구현은 작고 우아합니다.
정규식 기반 솔루션은 사전에서 가능한 모든 값을 고려합니다. 성능이 가장 큰 제약이라면 인덱스를 구축하여 속도를 상당히 높일 수 있습니다.
각 색인 = 문자 일치 단어 세트의 색인을 포함하는 각 단어 길이에 대한 색인으로 시작할 수 있습니다. 길이가 5 단어 인 경우 (예 : 2=r : {write, wrote, drate, arete, arite}, 3=o : {wrote, float, group}, 등) 원래 쿼리에 대해 가능한 일치 항목을 가져 오려면 '? ro ??'라고 말하면 단어 집합이 교차되어이 {wrote, group}경우에 결과가 발생합니다.
이것은 유일한 와일드 카드가 단일 문자이고 단어 길이가 앞에 있다고 가정합니다. 이것이 유효한 가정이 아니라면 이 백서 에서 논의 된 것과 같이 n-gram 기반 텍스트 일치를 권장 할 수 있습니다 .
원하는 데이터 구조를 trie 라고합니다 . 간단한 요약 은 wikipedia 문서 를 참조하세요 .
trie는 트리를 통과하는 경로가 인코딩하려는 모든 단어 세트를 형성하는 트리 구조입니다. 각 노드는 다음 문자 위치에서 가능한 각 문자에 대해 최대 26 개의 하위를 가질 수 있습니다. 내가 의미하는 바를 보려면 wikipedia 기사의 다이어그램을 참조하십시오.
삼항 검색 트리 사용을 고려해 보셨습니까 ? 조회 속도는 트라이와 비슷하지만 공간 효율적입니다.
이 데이터 구조를 여러 번 구현했으며 대부분의 언어에서 매우 간단한 작업입니다.
내 첫 번째 게시물에는 Jason이 발견 한 오류가 있었는데, 언제 잘 작동하지 않았습니까? 처음에있었습니다. 나는 지금 Anna에게서주기적인 교대를 빌렸다 ..
내 솔루션 : 단어 끝 문자 (@)를 도입하고 모든 순환 이동 단어를 정렬 된 배열에 저장 !! 각 단어 길이에 대해 하나의 정렬 된 배열을 사용하십시오. "th ?? e @"를 찾을 때 문자열을 이동하여?-마크를 끝으로 이동하고 (e @ th ?? 획득) 길이가 5 인 단어가 포함 된 배열을 선택하고 발생하는 첫 번째 단어에 대해 이진 검색을 수행합니다. 문자열 "e @ th"뒤에. 배열의 나머지 단어는 모두 일치합니다. 즉, "e @ thoo (thoose), e @ thes (these) 등)을 찾습니다.
솔루션에는 시간 복잡도 Log (N)가 있습니다. 여기서 N은 사전의 크기이며 데이터 크기를 6 배 정도 (평균 단어 길이) 확장합니다.
방법은 다음과 같습니다.
- 사전의 단어를 단어가 아닌 문자로 구분 된 하나의 긴 문자열로 연결합니다.
- Put all words into a TreeMap, where the key is the word and the value is the offset of the start of the word in the big String.
- Find the base of the search string; i.e. the largest leading substring that doesn't include a
'?'. - Use
TreeMap.higherKey(base)andTreeMap.lowerKey(next(base))to find the range within the String between which matches will be found. (Thenextmethod needs to calculate the next larger word to the base string with the same number or fewer characters; e.g.next("aa")is"ab",next("az")is"b".) - Create a regex for the search string and use
Matcher.find()to search the substring corresponding to the range.
Steps 1 and 2 are done beforehand giving a data structure using O(NlogN) space where N is the number of words.
This approach degenerates to a brute-force regex search of the entire dictionary when the '?' appears in the first position, but the further to the right it is, the less matching needs to be done.
EDIT:
To improve the performance in the case where '?' is the first character, create a secondary lookup table that records the start/end offsets of runs of words whose second character is 'a', 'b', and so on. This can be used in the case where the first non-'?' is second character. You can us a similar approach for cases where the first non-'?' is the third character, fourth character and so on, but you end up with larger and larger numbers of smaller and smaller runs, and eventually this "optimization" becomes ineffective.
An alternative approach which requires significantly more space, but which is faster in most cases, is to prepare the dictionary data structure as above for all rotations of the words in the dictionary. For instance, the first rotation would consist of all words 2 characters or more with the first character of the word moved to the end of the word. The second rotation would be words of 3 characters or more with the first two characters moved to the end, and so on. Then to do the search, look for the longest sequence of non-'?' characters in the search string. If the index of the first character of this substring is N, use the Nth rotation to find the ranges, and search in the Nth rotation word list.
A lazy solution is to let SQLite or another DBMS do the job for you.
Just create an in-memory database, load your words and run a select using the LIKE operator.
Summary: Use two compact binary-searched indexes, one of the words, and one of the reversed words. The space cost is 2N pointers for the indexes; almost all lookups go very fast; the worst case, "??e", is still decent. If you make separate tables for each word length, that'd make even the worst case very fast.
Details: Stephen C. posted a good idea: search an ordered dictionary to find the range where the pattern can appear. This doesn't help, though, when the pattern starts with a wildcard. You might also index by word-length, but here's another idea: add an ordered index on the reversed dictionary words; then a pattern always yields a small range in either the forward index or the reversed-word index (since we're told there are no patterns like ?ABCD?). The words themselves need be stored only once, with the entries of both structures pointing to the same words, and the lookup procedure viewing them either forwards or in reverse; but to use Python's built-in binary-search function I've made two separate strings arrays instead, wasting some space. (I'm using a sorted array instead of a tree as others have suggested, as it saves space and goes at least as fast.)
Code:
import bisect, re
def forward(string): return string
def reverse(string): return string[::-1]
index_forward = sorted(line.rstrip('\n')
for line in open('/usr/share/dict/words'))
index_reverse = sorted(map(reverse, index_forward))
def lookup(pattern):
"Return a list of the dictionary words that match pattern."
if reverse(pattern).find('?') <= pattern.find('?'):
key, index, fixup = pattern, index_forward, forward
else:
key, index, fixup = reverse(pattern), index_reverse, reverse
assert all(c.isalpha() or c == '?' for c in pattern)
lo = bisect.bisect_left(index, key.replace('?', 'A'))
hi = bisect.bisect_right(index, key.replace('?', 'z'))
r = re.compile(pattern.replace('?', '.') + '$')
return filter(r.match, (fixup(index[i]) for i in range(lo, hi)))
Tests: (The code also works for patterns like ?AB?D?, though without the speed guarantee.)
>>> lookup('hello')
['hello']
>>> lookup('??llo')
['callo', 'cello', 'hello', 'uhllo', 'Rollo', 'hollo', 'nullo']
>>> lookup('hel??')
['helio', 'helix', 'hello', 'helly', 'heloe', 'helve']
>>> lookup('he?l')
['heal', 'heel', 'hell', 'heml', 'herl']
>>> lookup('hx?l')
[]
Efficiency: This needs 2N pointers plus the space needed to store the dictionary-word text (in the tuned version). The worst-case time comes on the pattern '??e' which looks at 44062 candidates in my 235k-word /usr/share/dict/words; but almost all queries are much faster, like 'h??lo' looking at 190, and indexing first on word-length would reduce '??e' almost to nothing if we need to. Each candidate-check goes faster than the hashtable lookups others have suggested.
This resembles the rotations-index solution, which avoids all false match candidates at the cost of needing about 10N pointers instead of 2N (supposing an average word-length of about 10, as in my /usr/share/dict/words).
You could do a single binary search per lookup, instead of two, using a custom search function that searches for both low-bound and high-bound together (so the shared part of the search isn't repeated).
If you only have ? wildcards, no * wildcards that match a variable number of characters, you could try this: For each character index, build a dictionary from characters to sets of words. i.e. if the words are write, wrote, drate, arete, arite, your dictionary structure would look like this:
Character Index 0:
'a' -> {"arete", "arite"}
'd' -> {"drate"}
'w' -> {"write", "wrote"}
Character Index 1:
'r' -> {"write", "wrote", "drate", "arete", "arite"}
Character Index 2:
'a' -> {"drate"}
'e' -> {"arete"}
'i' -> {"write", "arite"}
'o' -> {"wrote"}
...
If you want to look up a?i?? you would take the set that corresponds to character index 0 => 'a' {"arete", "arite"} and the set that corresponds to character index 2 = 'i' => {"write", "arite"} and take the set intersection.
If you seriously want something on the order of a billion searches per second (though i can't dream why anyone outside of someone making the next grand-master scrabble AI or something for a huge web service would want that fast), i recommend utilizing threading to spawn [number of cores on your machine] threads + a master thread that delegates work to all of those threads. Then apply the best solution you have found so far and hope you don't run out of memory.
An idea i had is that you can speed up some cases by preparing sliced down dictionaries by letter then if you know the first letter of the selection you can resort to looking in a much smaller haystack.
Another thought I had was that you were trying to brute-force something -- perhaps build a DB or list or something for scrabble?
'program tip' 카테고리의 다른 글
| 암시 적으로 'string'형식을 'System.Threading.Tasks.Task로 변환 할 수 없습니다. (0) | 2020.12.14 |
|---|---|
| Laravel이 블레이드 템플릿의 모든 HTML을 이스케이프 (0) | 2020.12.14 |
| SO_REUSEADDR (setsockopt 옵션)-Linux의 의미는 무엇입니까? (0) | 2020.12.14 |
| JavaScript에서 새로 추가 된 요소에 onclick 이벤트 추가 (0) | 2020.12.14 |
| jQuery, .each를 사용하여 클래스의 각 요소 ID를 얻습니까? (0) | 2020.12.14 |