가장 빠른 방법은 파이썬

Question

에서 패턴의 첫 번째 항목에 대한 데이터의 문자열을 +

당신이 뭔가에 해당하는 것으로 가정 할 수있다 임의의 데이터의 1 기가 바이트 문자열있다 :

1_gb_string=os.urandom(1*gigabyte) 

우리는 할 것이다 고정 폭의 무한 수인 1 킬로바이트 패턴 1_kb_pattern에 대해이 문자열 1_gb_string을 검색합니다. 우리가 패턴을 찾을 때마다 다를 것입니다. 따라서 캐싱 기회는 분명하지 않습니다. 동일한 1 기가 바이트 문자열이 반복해서 검색됩니다. 다음은 어떤 일이 일어 났는지 설명하는 간단한 생성기입니다.

def findit(1_gb_string): 
    1_kb_pattern=get_next_pattern() 
    yield 1_gb_string.find(1_kb_pattern) 

패턴의 첫 번째 항목 만 찾아야합니다. 그 후에는 다른 주요 처리를 수행하지 않아야합니다.

1GB 이상의 데이터 문자열과 비교하여 1KB 패턴을 찾는 데 Python의 bultin 찾기보다 빠르다면 무엇을 사용할 수 있습니까?

(I 문자열을 분할 병렬를 검색하는 방법을 이미 알고, 그래서 당신은 그 기본 최적화를 무시할 수 있습니다.)

업데이트 : 16GB의 메모리 요구 사항을 행하십시오.

Answer 1

무한 메모리를 사용하면 모든 1k 문자열을 1GB 파일의 위치와 함께 해싱 할 수 있습니다.

무한 메모리보다 작 으면 검색 할 때 몇 개의 메모리 페이지를 만지게 될 것입니다.

Answer 2

하위 문자열을 찾기 위해 유전학 분야에서 사용되는 많은 문자열 일치 알고리즘이 있습니다. 시도해보십시오 this paper 또는 this paper

Answer 3

문자열을 사전 처리하는 데 많은 시간을 할애 할 의향이 있습니까?

당신이 할 수있는 일은 오프셋이있는 n 그램 목록을 만드는 것입니다.

알파벳이 16 진수이고 1 그램을 사용한다고 가정합니다.

그런 다음 00-FF를 들어, 당신은 당신이 문자열을 걸어이 (죄송 perlese)과 같은 사전

$offset_list{00} = @array_of_offsets 
$offset_list{01} = #...etc 

를 만들 수 있습니다 바이트 일이 모든 점에서 @array_of_offsets을 구축 할 수 있습니다. 임의의 n 그램에 대해이 작업을 수행 할 수 있습니다.

걷는 데 사용할 수있는 "검색 시작 지점"을 제공합니다.

물론, 단점은 문자열을 사전 처리해야한다는 것입니다.

편집 :

---

여기에 기본적인 아이디어는 접두사와 일치하는 것입니다. 정보가 매우 비슷하다면 심하게 폭탄을 터뜨릴 수 있지만, n-gram 사이에 상당한 양의 발산이 있으면 접두사를 잘 일치시킬 수 있어야합니다.

분석하고있는 정보의 종류에 대해 언급하지 않았으므로 발산을 정량화합시다.이 알고리즘의 목적 상 발산을 거리 함수로 특성화 할 수 있습니다. 높이 Hamming distance이 필요합니다. n-gram 사이의 해밍 거리가 1이라고하면, 위의 아이디어는 작동하지 않습니다. 하지만 n-1이면 위의 알고리즘이 훨씬 쉽습니다. 우리는 주어진 N 그램의 정보를 정의하는 Shannon Entropy를 호출 할 수 있습니다

:

은 이제 가능성의 일부 연속적인 제거를 수행하는 알고리즘을 만들어 보자, 내 알고리즘을 개선합니다. 검색 문자열을 가져 와서 처음 m자를 기준으로 접두사를 연속적으로 작성하십시오. m- 접두어의 엔트로피가 '충분히 높음'이면 나중에 사용하십시오.

1. 은
2. 이 1GB에 문자열을 검색하고 페이지를 일치 오프셋 (offset)의 배열을 만들려면 검색 문자열의 m-접두사로 페이지를 정의합니다.
3. m- 접두어를 k- 접두사, k> m, m- 접두사보다 높은 k- 접두사의 엔트로피로 확장합니다.
4. k- 접두어 문자열과 일치하도록 위에 정의 된 요소 오프셋 배열을 유지합니다. 일치하지 않는 요소를 버립니다.
5. 전체 검색 문자열이 충족 될 때까지 4로 이동하십시오.

의미에서 이것은 허프만 인코딩을 뒤집는 것과 같습니다.

Answer 4

나는 문자열에 대한 find() 방법은 search() 파이썬의 re (정규 표현식)에 의해 제공 방법 모듈보다 빠른 경우 확실히 모르겠지만, 알아내는 하나의 방법이있다. , 당신이 정말로 첫 번째 경기를하려면

import re 
def findit(1_gb_string): 
    yield re.search(1_kb_pattern, 1_gb_string) 

그러나, 당신은 반복자를 반환 finditer()를 사용하여 더 나을 수 있습니다 : 당신은 그냥 문자열을 검색하는 경우

은, 당신이 원하는 것은 이것이다 그러한 대규모 작업이 실제로 더 나을 수도 있습니다.

Answer 5

http://www.youtube.com/watch?v=V5hZoJ6uK-s 당신에게 가장 가치있을 것입니다. 그것의 MIT 강의에 대한 동적 프로그래밍

Answer 6

내가 아는 한, 표준 찾기 알고리즘은 n * m 비교에 대해 복잡성이있는 단순한 알고리즘입니다. 왜냐하면 은 가능한 모든 오프셋에 대해 패턴을 검사하기 때문입니다. n + m 비교가 필요한 좀 더 효과적인 알고리즘이 있습니다. 문자열이 자연 언어 문자열이 아닌 경우 Knuth–Morris–Pratt algorithm을 시도 할 수 있습니다. Boyer-Moore 검색 알고리즘은 빠르고 간단합니다.

Answer 7

패턴이 상당히 임의 인 경우 문자열의 n 접두어 위치를 미리 계산할 수 있습니다.

n 접두어에 대한 모든 옵션을 사용하지 않고 1GB 문자열에서 실제 옵션을 사용하십시오. 그 중 1Gig 미만이됩니다. 귀하의 메모리에 맞는 접두어로 사용하십시오. 16GB RAM이 없지만 3이나 심지어 2가 아니라면 4의 접두어가 작동 할 수 있습니다 (적어도 메모리 효율적인 데이터 구조에서).

임의의 1GB 문자열과 무작위 1KB 패턴의 경우 3 바이트 접두사를 사용하는 경우 접두사 당 몇 개의 위치를 ​​가져야하지만 4 바이트 접두사는 평균 0 또는 1을 가져야하므로 조회가 빨라야합니다.

미리 계산 위치

def find_all(pattern, string): 
    cur_loc = 0 
    while True: 
    next_loc = string.find(pattern, cur_loc) 
    if next_loc < 0: return 
    yield next_loc 
    cur_loc = next_loc+1 

big_string = ... 
CHUNK_SIZE = 1024 
PREFIX_SIZE = 4 
precomputed_indices = {} 
for i in xrange(len(big_string)-CHUNK_SIZE): 
    prefix = big_string[i:i+PREFIX_SIZE] 
    if prefix not in precomputed_indices: 
    precomputed_indices[prefix] = tuple(find_all(prefix, big_string)) 

당신이 그렇게 오래 틱 전처리이 허용 명확하게, 나는이 Rabin-Karp의 변형을 건의 할 것

def find_pattern(pattern): 
    prefix = pattern[:PREFIX_SIZE] 
    # optimization - big prefixes will result in many misses 
    if prefix not in precomputed_indices: 
    return -1 
    for loc in precomputed_indices[prefix]: 
    if big_string[loc:loc+CHUNK_SIZE] == pattern: 
     return loc 
    return -1 

Answer 8

패턴 찾기 :의 "를 위키피디아 (Wikipedia)가 말한 것처럼 다중 패턴 검색을위한 선택 알고리즘 "

haystack[x:x+N]의 해시를 알고있는 경우 haystack[x+1:x+N+1]의 해시 계산은 O (1) 인 "롤링 해시"함수를 정의하십시오. (파이썬에 내장 된 hash과 같은 일반 해싱 함수에는이 속성이 없기 때문에 직접 작성해야합니다. 그렇지 않으면 전처리가 exhaustfully이됩니다. 다항식 접근법은 유익하며 30 비트 해시 결과를 사용할 수 있습니다 (필요한 경우 마스킹을 사용합니다. 즉, 더 정밀한 계산을 수행하고 마스크 된 30 비트의 선택 항목 만 저장할 수 있습니다). 명료성을 위해이 롤링 해시 함수를 RH라고합시다.

따라서, 건초 더미 1GB 문자열을 굴릴 때 1G RH 결과를 계산하십시오. 이것들을 저장했다면 인덱스 - 인 - 건초 더미 -> RH 값을 매핑하는 1G 30 비트 값 (4GB)의 배열 H를 얻을 수 있습니다. 그러나 역 매핑을 원하므로 각 RH 값에 대해 2x30 항목 (1G 항목)의 배열 A를 사용하여 건초 더미에서 관심있는 모든 색인을 제공합니다 (RH 값이 나타나는 색인). 각 항목에 대해 첫 번째 가능한 흥미로운 건초 더미 인덱스의 인덱스를 1G 인덱스의 다른 배열 B에 저장합니다.이 인덱스는 모든 인덱스를 동일한 RH 값 (해싱 조건의 충돌)이 인접한 건초 스택으로 유지하도록 주문됩니다. H, A 및 B는 각각 4 바이트의 1G 항목을 가지므로 총 12GB입니다.

들어오는 1K 바늘 각각에 대해 RH를 계산하여 k라고하고 A로 색인으로 사용합니다. A [k]는 B와 비교할 가치가있는 첫 번째 인덱스 b를 제공합니다. 따라서, 좋은 RH의 당신은 충돌이 거의 없어야하므로, while은 어떤 방법 으로든 돌아올 때까지 매우 자주 실행되어야합니다. 그래서 각각의 바늘 찾기는 정말 빨라야합니다.

Answer 9

풍부한 RAM (또는 가능하면 디스크/스왑)을 사용할 수 있다면 누군가 색인을 생성 할 수있는 가능성을 암시합니다.

원래 Gig 문자열의 각 문자에서 확장 된 1K 블록에서 간단한 32 비트 CRC를 수행했다고 가정 해보십시오. 이렇게하면 데이터 시작 부분에서 각 바이트 오프셋에 대해 4 바이트의 체크섬 데이터가 생성됩니다.

그 자체로 검색 속도가 약간 향상 될 수 있습니다. 각 1K 검색 대상의 체크섬은 각 CRC가 실제 일치에 대해 테스트 한 각 CRC에 대해 검사 할 수 있습니다. 그것은 정상적인 선형 검색보다 몇 배 빠른 속도입니다.

분명히 CRC 배열 (원본 데이터의 원래 Gig과 환경 및 프로그램의 오버 헤드)에 4GB의 RAM이 필요합니다.

~ 16GB가 있으면 체크섬을 정렬하고 각 체크섬이있는 곳에서 오프셋 목록을 저장할 수 있습니다. 그것은 색인 된 검색이됩니다 (타겟 검색 당 약 16 개의 프로브 평균 ... 32 또는 33 주변의 최악의 경우 (울타리 포스트 일 수 있음).

16BG 파일 인덱스가 선형 체크섬 검색보다 우수한 성능을 제공하고 파일 시스템/스토리지가 매우 느린 경우가 아니면 선형 원시 검색보다 거의 확실합니다.

(추가) :이 전략은 동일한 1 기가 바이트 데이터 블로 브에서 많은 검색을 수행해야한다고 설명했기 때문에이 전략이 유용하다는 것을 분명히해야합니다.

색인 생성 (체크섬을 수행하는 여러 스레드가있을뿐만 아니라 읽기 동안) 스레드 작성 방법을 사용하여 색인을 작성할 수 있습니다. 인덱스를 별도의 프로세스 또는 노드 클러스터로 오프로드 할 수도 있습니다 (특히 위에 설명 된 ~ 16GB 옵션 인 파일 기반 인덱스를 사용하는 경우). 간단한 32 비트 CRC를 사용하면 판독기 스레드가 데이터를 가져올 수있는 속도로 체크섬/인덱싱을 빠르게 수행 할 수 있습니다 (그러나 데이터의 각 1K에 대해 1024 개의 체크섬을 말하는 것이므로 그렇지 않을 수 있습니다).

실제로 검색을 수행하기 위해 파이썬 모듈을 C로 코딩하여 성능을 향상시킬 수 있습니다. 체크섬/색인 생성을 수행 할 수도 있습니다.

이러한 C 확장의 개발 및 테스트에는 다른 절충안이 필요합니다. 재사용 성이 거의없는 것처럼 들립니다.

Answer 10

효율적이지만 복잡한 방법 중 하나는 full-text indexing with the Burrows-Wheeler transform입니다. 소스 텍스트에서 BWT를 수행 한 다음 작은 인덱스를 사용하여 입력 패턴과 일치하는 텍스트의 하위 문자열을 빠르게 찾습니다.

이 알고리즘의 시간 복잡도는 대략 일치하는 문자열의 길이가 O (n)이고 입력 문자열의 길이와 관계가 없습니다! 또한 인덱스의 크기는 입력 데이터보다 훨씬 크지 않으며 압축은 소스 텍스트의 크기보다 작게 줄일 수도 있습니다.