python - 추출 - 파이썬 패턴매칭




파이썬에서 패턴의 첫 번째 발생에 대한 1GB+데이터 문자열을 검색하는 가장 빠른 방법 (7)

long-ish 전처리가 용인 할 수 있음을 분명히하면서, Rabin-Karp 의 변종을 제안 할 것입니다. "여러 패턴 검색을위한 선택 알고리즘"입니다. 위키 피 디아가 말했듯이.

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

그래서 건초 더미 1GB 문자열을 따라 굴러 갈 때 RH 결과의 1G를 계산하십시오. 이것들을 저장했다면 인덱스 - 인 - 건초 더미 -> RH 값을 매핑하는 1G 30 비트 값 (4GB)의 배열 H를 얻을 수 있습니다. 그러나 당신은 역 매핑을 원하므로 각 RH 값에 대해 haystack (해당 RH 값이 발생하는 인덱스)의 모든 인덱스를 제공하는 2 ** 30 항목 (1G 항목)의 배열 A를 대신 사용하십시오. 각 항목에 대해 첫 번째 가능한 흥미로운 건초 더미 색인의 색인을 1G 색인의 다른 배열 B에 저장합니다.이 색인은 모든 색인을 동일한 RH 값 (해싱 용어의 "충돌")을 가진 건초 더미에 인접하게 유지하도록 명령 된 건초 더미에 인접합니다. H, A 및 B는 각각 4 바이트의 1G 항목을 가지므로 총 12GB입니다.

이제 들어오는 1K 바늘마다 RH를 계산하여 k라고 부르고 A로 색인으로 사용합니다. A [k]는 B와 비교할 가치가있는 첫 번째 인덱스 b를 제공합니다. 그렇게해라.

ib = A[k]
b = B[ib]
while b < len(haystack) - 1024:
  if H[b] != k: return "not found"
  if needle == haystack[b:b+1024]: return "found at", b
  ib += 1
  b = B[ib]

좋은 RH의 당신은 충돌이 거의 없어야합니다. 그래서 한 동안이나 다른 것을 돌려 줄 때까지는 몇 번만 실행해야합니다. 그래서 각각의 바늘 찾기는 정말 빨라야합니다.

임의의 데이터로 구성된 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)

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

파이썬의 bultin이 1KB 이상의 데이터 문자열과 1KB 패턴을 비교하는 것보다 더 빨리 사용할 수 있습니까?

(나는 이미 문자열을 분할하고 병렬로 검색하는 방법을 이미 알고 있으므로 기본 최적화를 무시할 수 있습니다.)

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


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


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

무한한 메모리보다 적 으면 검색 할 때 얼마나 많은 메모리 페이지를 건드릴 것인가에 달려 있습니다.


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

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

알파벳이 16 진수이고 1 그램을 사용한다고 가정 해보십시오.

그러면 00-ff에 대해 다음과 같은 사전을 만들 수 있습니다 (perlese, sorry).

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

여기서 문자열을 걸어 내려 가서 바이트가 발생하는 모든 지점에서 @array_of_offsets를 작성합니다. 임의의 n-gram에 대해이 작업을 수행 할 수 있습니다.

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

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

편집하다:

기본 아이디어는 접두어와 일치시키는 것입니다. 정보가 매우 비슷하다면 심하게 폭탄을 터뜨릴 수 있지만, n-gram 사이에 분명한 차이가 있다면 접두어를 잘 매치 할 수 있어야합니다.

분석하고있는 정보의 종류에 대해 논의하지 않았으므로 차이를 정량화합시다. 이 알고리즘의 목적을 위해 발산을 거리 함수로 특성화 할 수 있습니다 . 해밍 거리를 상당히 높게 설정해야합니다. n-gram 사이의 해밍 거리가 1이라고하면, 위의 아이디어는 작동하지 않습니다. 하지만 n-1이면 위의 알고리즘이 훨씬 쉽습니다.

내 알고리즘을 향상시키기 위해 가능한 한 연속적으로 제거하는 알고리즘을 작성해 보겠습니다.

주어진 n-gram의 정보를 정의하기 위해 Shannon Entropy 를 호출 할 수 있습니다. 검색 문자열을 가져 와서 처음 m자를 기준으로 접두어를 연속적으로 작성하십시오. m 접두어의 엔트로피가 '충분히 높다'는 경우 나중에 사용하십시오.

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

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


파이썬의 re (정규 표현식) 모듈에서 제공하는 search() 메소드보다 문자열에 대한 find() 메소드가 빠르다는 것을 확실하게 알 find() 는 없지만 알아낼 수있는 방법은 하나뿐입니다.

문자열을 검색하는 경우 원하는 것은 다음과 같습니다.

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

그러나 실제로 첫 번째 일치 만 원할 경우 finditer() 를 반환하는 finditer() 를 사용하는 것이 더 나을 것입니다. 이러한 큰 작업이 실제로 더 좋을 수도 있습니다.


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

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

임의의 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))

패턴을 찾는다.

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





large-data-volumes