파일의 모든 기호의 빈도를 계산하는 더 좋은 방법이 있습니까?

좋아요, 그렇다면 가능한 모든 기호가 포함되지 않은 텍스트 파일이 있고 각 기호의 빈도를 계산하고 빈도를 계산 한 후 각 기호와 해당 빈도에 액세스해야한다고 가정하십시오. 가장 빈번한 빈번한 빈번한. 기호는 반드시 ASCII 문자 일 필요는 없지만 모든 길이가 같지만 임의의 바이트 시퀀스 일 수 있습니다.파일의 모든 기호의 빈도를 계산하는 더 좋은 방법이 있습니까?

function add_to_heap (symbol) 
    freq = heap.find(symbol).frequency 
    if (freq.exists? == true) 
     freq++ 
    else 
     symbol.freq = 1 
     heap.insert(symbol) 

MaxBinaryHeap heap 
while somefile != EOF 
    symbol = read_byte(somefile) 
    heap.add_to_heap(symbol) 
heap.sort_by_frequency() 

while heap.root != empty 
    root = heap.extract_root() 
    do_stuff(root)

궁금 : 각 기호 파일에서 발생하는 횟수를 더 나은, 더 간단한 계산하는 방법 및 저장이 나는 (의사)에이 같은 일을 고려하고

출처

2011-10-04 rps

O (1) 빈도 검색을 제공하지만 가장 자주 자주 사용하는 결과가없는 해시 맵 또는 검색 트리/힙을 사용하여 O (lg n) 삽입 및 검색을 수행하지만 최소 빈도로) 결과. –

힙에서 임의의 노드를 찾는 것이 다소 비용이 많이 들기 때문에 바이너리 힙이 특히 좋은 데이터 구조는 아닙니다. 다른 사람이 지적했듯이 이진 트리 나 해시 테이블을 사용하는 것이 좋습니다. –

항상 힙의 HashMap isntead를 사용할 수 있습니다. 이렇게하면 O (log n) 대신에 발견 된 각 기호에 대해 O (1)에있는 작업을 수행하게됩니다. n은 현재 힙에있는 항목의 수입니다.

그러나 별개의 기호가 합리적인 숫자로 묶인 경우 (1 바이트가 이상적이고 2 바이트가 여전히 양호해야 함), 그 크기의 배열을 사용하고 다시 O (1)을 사용할 수 있지만 현저하게 낮은 일정 비용. 당신은 시간을 실행에 따라 "최고"솔루션을 찾고 있다면

출처

2011-10-04 19:09:27

, 여기에 내가 좋을 것 무엇 : 파일을 읽는 경우

, 당신은 당신의 기호를 기준으로 정렬 (또는 해시)가 있어야합니다 기호 그 자체의 가치이지 빈도가 아닙니다. 이렇게하면 전체 목록을 검색하지 않고 이미 본 기호 목록에서 현재 기호를 빠르게 찾을 수 있습니다. 당신은 또한 초기 구조가 빠른 삽입을 수행 할 수 있어야합니다 - 나는 해시의 이진 트리를 권하고 싶습니다.

모든 기호를 읽은 후에는 빈도 수에 따라 순서를 전환해야합니다. 모든 것을 배열로 읽어 들인 다음 내부 정렬을 수행 하겠지만,이를 수행 할 수있는 동등한 방법이 있습니다.

희망이 도움이됩니다.

출처

2011-10-04 19:13:42

파일의 모든 기호의 빈도를 계산하는 더 좋은 방법이 있습니까?

답변

관련 문제