다른 문자열에 나타나는 문자열의 수

Question

변경되지 않는 큰 정적 바이너리 (10GB)가 있습니다.

작은 문자열 (각각 15 바이트 이하)을 입력 한 다음 가장 빈번한 문자열을 결정할 수 있기를 원합니다.

사실이 바이너리 전체를 검색하지 않고서는이 값을 정확하게 결정할 수 없다는 것을 알고 있으므로 근사치가 될 것입니다.

트리/해시 테이블을 작성하는 것은 대략 256^15 바이트가 필요하기 때문에 가능하지 않습니다.

이 작업에는 약 100GB의 디스크 공간과 8GB의 RAM이 있지만 실제로 파일을 넘기지 않고이 작업을 수행하는 방법을 찾을 수 없습니다.

나는 큰 바이너리를 준비하기 위해 많은 시간을 가지고있다. 그리고 나서 나는 가장 빈번한 문자열이 무엇인지를 여러 번 결정할 필요가있다.

아이디어가 있으십니까?

감사합니다. 다니엘.

: 당신이 스토리지를 감당할 수

Answer 1

아마 많은 N-튜플의 개수와 해시 테이블을 구축 (BTW가 중요한 경우, 파이썬 사용하고 있습니다)? 더 이상 나타나지 않는 나무를자를 수 있습니다. 나는 그것을 "근사치"라고 부르지 않을 것이지만, "상한"이 될 수 있으며, 나타나지 않는 문자열을 탐지 할 수 있습니다.

그래서 모든 4 개 튜플을 빌드 할 수 있다고 가정 해보십시오.

그런 다음 "ABCDEF"의 발생 횟수를 계산하려면 최소 카운트 (ABCD), 카운트 (BCDE), 카운트 (CDEF)가 필요합니다. 그 중 하나라도 0이면 문자열이 표시되지 않습니다. 그것이 하나라면 최대 한 번 나타납니다 (그러나 전혀 아닐 수도 있음).

Answer 2

정적 문자열이 커서 변경되지 않으므로이 문자열을 전처리하는 일회성 작업을 구별 할 수 있으므로 쿼리 응답 작업에서 반복해서 사용할 필요가 없습니다. 보다 강력한 머신에서 일회성 작업을 수행하는 것이 편리 할 수 ​​있습니다.

크기가 더 큰 내부 저장소가있는 컴퓨터를 찾을 수 있으면 접미어 배열 - 오프셋에서 시작하는 접미사의 정렬 된 순서로 스트림에 대한 오프셋 배열을 작성할 수 있습니다. 이것은 쿼리를 위해 외부 저장소에 저장 될 수 있으며 바이너리 검색과 함께이 쿼리 문자열을 사용하여 쿼리 문자열이 나타나는 정렬 된 순서의 첫 번째 및 마지막 위치를 찾을 수 있습니다. 두 개 사이의 거리는 분명히 발생 횟수를 알려줄 것이며 바이너리 검색은 16Gbyte를 2^34 바이트로 가정 할 때 약 34 개의 바이너리 찹 (chops)을 필요로하므로 각각의 쿼리는 약 68 개의 디스크 검색 비용을 부담해야합니다.

내부 저장 용량을 찾을 수는 없겠지만 1TB USB 하드 드라이브를 약 50 파운드에 구입 했으므로 한 번만 외장 스토리지를 늘릴 수 있다고 생각합니다. 외부 메모리에는 접미사 배열을 만드는 알고리즘이 있지만 쿼리 문자열이 15 바이트로 제한되어 있기 때문에 복잡한 작업이 필요하지 않습니다. 모든 오프셋에서 발견 된 15 바이트 문자열을 5 바이트 오프셋 번호 다음에 쓰고 200 바이트의 데이터를 작성한 다음 외부 정렬을 사용하여 이러한 20 바이트 레코드를 정렬하면됩니다. 이렇게하면 쿼리에 응답하기 위해 외부 저장소에 넣을 수 있도록 정렬 된 순서로 문자열에 50GB의 인덱스가 제공됩니다.

Answer 3

미리 쿼리를 모두 알고 있거나 일괄 처리 할 준비가되어 있다면 다른 방법으로 http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm 트리를 작성하는 것이 좋습니다. 이것은 질의의 전체 크기에서 선형적인 시간을 필요로합니다. 그런 다음 해당 데이터의 크기와 문자열이 일치하는 횟수를 합한 시간에 비례하여 10GB 이전의 데이터를 스트리밍 할 수 있습니다.

Answer 4

당신이 가장 자주 찾고 있기 때문에 대략적인 해결책을 받아 들일 용의가 있습니다. 해시 테이블 대신 일련의 Bloom filters을 사용할 수 있습니다. 충분히 큰 값을 사용하는 경우에는 가양 성 비율을 낮게 유지할 수 있으므로 쿼리 크기에 대해 걱정할 필요가 없습니다.

아이디어는 가능한 모든 쿼리 크기를 거쳐 하위 문자열을 만드는 것입니다. 예를 들어, 쿼리가 3과 100 사이에 있으면 비용이 발생할 것입니다 (N * (i = 3에서 i = 100까지의 합)). 그런 다음 하나씩 블룸 필터 중 하나에 하위 집합을 추가하여 쿼리가 필터 내에 존재하지 않게하여 필요한 경우 동일한 해시 함수를 사용하여 새로운 하나의 블룸 필터를 만듭니다. 각 필터를 검토하고 그 안에 쿼리가 있는지 확인하여 카운트를 얻습니다. 그런 다음 각 쿼리는 필터의 각 항목을 통과하여 필터가 있는지 여부를 확인합니다. 필터가 있으면 개수에 1을 더합니다.

위양성 비율과 필터 수의 균형을 조정해야합니다. 필터 중 하나에서 위양성 비율이 너무 높아지면 유용하지 않습니다. 마찬가지로 여러 블룸 필터를 사용하면 악의적입니다 (하위 문자열 당 하나의 필터 만 사용하면 가능합니다). 이러한 문제를 해결할 수있는 몇 가지 방법이 있습니다.

• 필터의 수를 줄이려면에만 너무 많은 왼쪽이 때까지
  1. 무작위로 필터를 삭제합니다. 이렇게하면 위음성 비율이 높아질 가능성이 높으므로 예상되는 위양성 비율이 가장 높은 필터를 단순히 삭제하는 것이 좋습니다.
  2. 필터가 무수히 병합 될 때까지 필터를 무작위로 병합합니다. 필터를 너무 자주 병합하지 않는 것이 오 탐지율을 높이는 이상적인 방법입니다. 실질적으로 말하면, 오진 가능성을 관리하기에는 너무 어려울 수 있으므로 확장 버전 (아래 참조)을 사용하지 않으면 너무 많은 작업을 수행 할 수 있습니다.
  3. 블룸 필터를 추가 할 때 욕심이 많은 접근법을 피하는 것도 좋지 않을 수 있습니다. 필터를 추가 할 때 다소 선택적입니다.

당신은 어쨌든 제안하고있는 무슨과 비슷한 소리를하는 관리 일을 계속 scalable bloom filters을 구현하는 데 끝날 수도, 잘 작동합니다.