긴 하위 문자열 목록 검색

Question

문제점 : ~ 250000 정수 사용자 집합과 JSON 형식의 한 행 레코드 당 약 테라 바이트가 주어지면 사용자 ID가 일치하는 레코드를 데이터베이스에로드하십시오 .

모든 레코드의 약 1 %만이 250000 사용자 ID와 일치합니다. JSON이 오랜 시간이 걸리는 각 레코드를 디코딩하는 대신 문자열 일치를 사용하여 사용자 ID가 원시 JSON에 있는지 확인하려고합니다. 일치하면 JSON이 디코딩되고 레코드가 검사 된 다음 삽입됩니다.

문제는 원시 JSON의 한 문자열과 ~ 250k 개의 문자열 항목이 포함 된 세트를 일치시키는 것이 느립니다.

다음 코드는 지금까지의 :이 올바른 방법으로 접근하고

// get the list of integer user IDs 
cur.execute('select distinct user_id from users') 

// load them as text into a set 
users = set([]) 
for result in cur.fetchall(): 
    users.add(str(result[0])) 

// start working on f, the one-json-record-per-line text file 
for line in f: 
    scanned += 1 
    if any(user in line for user in users): 
     print "got one!" 
     // decode json 
     // check for correct decoded user ID match 
     // do insert 

? 이 문자열을 더 빨리 일치시키는 방법은 무엇입니까? 현재, 많은 사용자 ID를 찾을 때 3 기가비트 컴퓨터에서 초당 ~ 2 항목을 관리합니다 (좋지 않음). 사용자 ID 목록이 매우 짧은 경우 초당 ~ 200000 개의 항목을 관리합니다. 매칭 알고리즘을 반전

Answer 1

Aho-Corasick이 목적을 위해 만들어진 것으로 보인다. 그것을위한 편리한 파이썬 모듈 (easy_install ahocorasick)조차있다.

import ahocorasick 

# build a match structure 
print 'init empty tree' 
tree = ahocorasick.KeywordTree() 

cur.execute('select distinct user_id from users') 

print 'add usernames to tree' 
for result in cur.fetchall(): 
    tree.add(str(result[0])) 

print 'build fsa' 
tree.make() 

for line in f: 
    scanned += 1 
    if tree.search(line) != None: 
     print "got one!" 

이렇게하면 초당 ~ 450 개의 항목에 더 가깝습니다.

Answer 2

봅니다 :

for digit_sequence in re.findall('[0-9]+', line): 
    if digit_sequence in users: 
     ... 

Answer 3

저는 C++ 프리랜서입니다. 제 클라이언트는 일반적으로 느린 파이썬/자바/.net/etc 코드가있는 벤처 기업입니다. 보통 x100 배 빠릅니다. 최근에는 테라 바이트 단위의 텍스트 데이터로 5 백만 개의 하위 문자열 검색을 구현하는 질문 작업과 비슷합니다.

몇 가지 알고리즘을 테스트했습니다. Aho-Corasick에게는 오픈 소스 http://sourceforge.net/projects/multifast/을 사용했습니다. 가장 빠른 알고리즘이 아니 었습니다. 가장 빠른 알고리즘은 해시 테이블과 Rabin-Karp 검색 알고리즘에서 얻은 몇 가지 아이디어를 혼합하여 만든 알고리즘입니다. 이 간단한 알고리즘은 AC보다 x5 배 빠르고 메모리 사용량이 x5 배 적습니다. 평균 하위 문자열 길이는 32 바이트입니다. 그래서, AC는 이것을위한 가장 빠른 골동품이 아닐 수도 있습니다.