0과 1이 교대로 반복되는 경우 텍스트를 실행으로 인코딩하십시오. n 0의 실행은 -n이고 n 1의 실행은 n입니다. 그런 다음 검색 문자열을 인코딩하십시오. 그런 다음 인코딩 된 문자열을 사용하는 검색 함수를 만듭니다.
코드는 다음과 같습니다 : 문자열에
try:
import psyco
psyco.full()
except ImportError:
pass
def encode(s):
def calc_count(count, c):
return count * (-1 if c == '0' else 1)
result = []
c = s[0]
count = 1
for i in range(1, len(s)):
d = s[i]
if d == c:
count += 1
else:
result.append(calc_count(count, c))
count = 1
c = d
result.append(calc_count(count, c))
return result
def search(encoded_source, targets):
def match(encoded_source, t, max_search_len, len_source):
x = len(t)-1
# Get the indexes of the longest segments and search them first
most_restrictive = [bb[0] for bb in sorted(((i, abs(t[i])) for i in range(1,x)), key=lambda x: x[1], reverse=True)]
# Align the signs of the source and target
index = (0 if encoded_source[0] * t[0] > 0 else 1)
unencoded_pos = sum(abs(c) for c in encoded_source[:index])
start_t, end_t = abs(t[0]), abs(t[x])
for i in range(index, len(encoded_source)-x, 2):
if all(t[j] == encoded_source[j+i] for j in most_restrictive):
encoded_start, encoded_end = abs(encoded_source[i]), abs(encoded_source[i+x])
if start_t <= encoded_start and end_t <= encoded_end:
return unencoded_pos + (abs(encoded_source[i]) - start_t)
unencoded_pos += abs(encoded_source[i]) + abs(encoded_source[i+1])
if unencoded_pos > max_search_len:
return len_source
return len_source
len_source = sum(abs(c) for c in encoded_source)
i, found, target_index = len_source, None, -1
for j, t in enumerate(targets):
x = match(encoded_source, t, i, len_source)
print "Match at: ", x
if x < i:
i, found, target_index = x, t, j
return (i, found, target_index)
if __name__ == "__main__":
import datetime
def make_source_text(len):
from random import randint
item_len = 8
item_count = 2**item_len
table = ["".join("1" if (j & (1 << i)) else "0" for i in reversed(range(item_len))) for j in range(item_count)]
return "".join(table[randint(0,item_count-1)] for _ in range(len//item_len))
targets = ['0001101101'*2, '01010100100'*2, '10100100010'*2]
encoded_targets = [encode(t) for t in targets]
data_len = 10*1000*1000
s = datetime.datetime.now()
source_text = make_source_text(data_len)
e = datetime.datetime.now()
print "Make source text(length %d): " % data_len, (e - s)
s = datetime.datetime.now()
encoded_source = encode(source_text)
e = datetime.datetime.now()
print "Encode source text: ", (e - s)
s = datetime.datetime.now()
(i, found, target_index) = search(encoded_source, encoded_targets)
print (i, found, target_index)
print "Target was: ", targets[target_index]
print "Source matched here: ", source_text[i:i+len(targets[target_index])]
e = datetime.datetime.now()
print "Search time: ", (e - s)
두 배 당신이 제공 한, 1 천만 자에 세 대상의 최초의 일치를 찾을 일곱 초 정도 걸립니다. 물론, 임의의 텍스트를 사용하고 있기 때문에, 각 실행마다 조금씩 다릅니다.
psyco는 런타임에 코드를 최적화하기위한 파이썬 모듈입니다. 이를 사용하면 뛰어난 성능을 얻을 수 있으며 C/C++ 성능의 상한선으로 추정 할 수 있습니다. 여기에 최근 실적은 다음과 같습니다
는
Make source text(length 10000000): 0:00:02.277000
Encode source text: 0:00:00.329000
Match at: 2517905
Match at: 494990
Match at: 450986
(450986, [1, -1, 1, -2, 1, -3, 1, -1, 1, -1, 1, -2, 1, -3, 1, -1], 2)
Target was: 1010010001010100100010
Source matched here: 1010010001010100100010
Search time: 0:00:04.325000
그것은에 대한 세 가지 인코딩 된 문자열을 검색하기 위해 1000 만 개 문자와 약 4 초를 인코딩하는 약 300 밀리 초 걸립니다. 나는 인코딩 시간이 C/C++에서 높을 것이라고 생각하지 않는다.
어떤 언어를 사용하고 계시거나 사용할 수 있습니까? 보다 확실한 알고리즘이 이미 구현되었습니다. (보너스 : 어떤 하드웨어를 사용하고 있습니까? 클라우드를 빌려보고 맵핑/문제를 줄입니다!) – pilcrow
C++. 지금 당장 내 프로그램은 몇 백 라인의 코드와 하나의 클래스로 구성되어 있습니다 ... 나는 더 단순한 것으로 유지하고 더 이상의 제 3 자 코드를 통합하지 않을 것입니다. – erjiang