제한된 메모리로 중복 문자열 제거

문자열 목록이 있고 전체 목록을 메모리에로드 할 수는 없지만 파일의 목록 부분을로드 할 수 있습니다. 이 문제를 해결하는 가장 좋은 방법은 무엇입니까?제한된 메모리로 중복 문자열 제거

2014-06-23 Oscar

파일의 크기는 어느 정도입니까? 메모리 제한은 무엇입니까? 대상 기계 및 언어는 무엇입니까? 어떤 종류의 문자열? 그들은 얼마나 오래? 얼마나 많은 중복이 예상됩니까? – 0xbe5077ed

외부 도구를 사용할 수 있다면 GNU/Linux'sort' 프로그램은 메모리보다 큰 파일을 정렬하고 중복을 제거 할 수 있습니다. 파일이 이미 정렬되어 있다면'uniq' 프로그램을보십시오. –

@ 0xbe5077ed :이 광범위한 질문 중 하나의 특정 사례는 다음과 같습니다. http://stackoverflow.com/questions/32535222/memory-constrained-external-sorting-of-strings-with-duplicates-combinedcounted –

한 가지 방법은 external sort을 사용하여 파일을 정렬 한 다음 정렬 된 목록에서 단일 반복으로 중복을 제거하는 것입니다. 이 방법은 디스크 공간이 거의 필요하지 않으며 디스크에 대한 액세스는 O(nlogn)입니다.

또 다른 접근법은 해싱을 기반으로합니다. 문자열의 해시 코드를 사용하고 해시 코드가 특정 범위에있는 모든 문자열을 포함하는 하위 목록을로드합니다. x이로드되고 복제본이있는 경우 해당 누수가 동일한 버킷에도로드됩니다.
디스크에 액세스하려면 O(n*#buckets)이 필요하지만 더 많은 메모리가 필요할 수 있습니다. 필요한 경우 다른 해시 함수를 사용하여 재귀 적으로 프로 시저를 호출 할 수 있습니다.

출처

2014-06-23 15:30:15 amit

외부 정렬에서 다음을 수행 할 수 있습니다. 알고리즘의 두 번째 (즉 병합) 통과 동안 중복을 제거하십시오. –

@JimMischel : pass1에서 배치 내에서 찾을 수있는 중복을 제거하면 병합 작업을 저장하는 배치를 줄일 수 있습니다. 또한 입력을 읽을 때 Trie 또는 DAWG를 작성하여 더 큰 pass1 배치를 정렬하여 지금까지 본 문자열 세트를 압축하여 표현할 수 있습니다 (프로세스에서 중복을 찾는 것). http://stackoverflow.com/questions/32535222/memory-constrained-external-sorting-of-strings-with-duplicates-combinedcounted/32537772#32537772에서 내 대답보기 –

내 솔루션은 외부 메모리 사용을 허용하는 병합 정렬을 수행하는 것입니다. 정렬 후에 중복을 검색하면 두 요소를 비교하는 것만 큼 쉬울 것입니다.

예 :

0 : 고양이 1 개 2 : 새 3 : 고양이 4 : 코끼리 5 : 고양이

병합 종류의

0 : 새 1 : 고양이 2 : 고양이 3 : 고양이 4 개 5 : 코끼리

다음은 0 & 1 -> 중복되지 않으므로 앞으로 이동하십시오. 2 -> 중복, 1 은 2 & 3 비교 (이 나중에 건너 뛸 빈 문자열로 채우는 것처럼 간단 할 수있다) 제거 -> 제거 2 등

1 &을 제거하는 이유 2보다 2 2 & 3이 더 효율적인 비교를 허용한다는 것입니다. 제거 된 인덱스를 건너 뛰지 않아도 걱정할 필요가 없습니다.

출처

2014-06-23 15:31:04 deckeresq

제한된 메모리로 중복 문자열 제거

답변

관련 문제