1
블록 정렬을 구현하려고합니다. 이것은 Burrows Wheeler paper에서 온 것입니다.접미사 정렬에 기수 정렬이 사용됩니까?
는
Q4 (이 단계 전에, 당신은 S의 V 접미사 배열을 만듭니다). [기수 정렬]
각 접미어의 처음 두 문자를 정렬 키로 사용하여 V의 요소를 정렬합니다. 이는 기수 정렬을 사용하여 효율적으로 수행 할 수 있습니다.
그래서 기수 정렬로 접미사를 정렬하는 것으로 알고 있습니다.
배열 V를 어떻게 업데이트해야합니까? 기수 정렬이 완료된 후에야 서 픽스의 정렬 된 위치를 알 수 있습니다. 네 번째 접미사가 정렬 된 후 첫 번째가된다고 가정합니다. 그래서 V [0] = i. 이 경우, 우리는 (내가 말했기 때문에) i = 4라는 것을 알고 있습니다. 그러나 알고리즘은 우리가 그들의 위치를 추적하지 않기 때문에 어떻게 알 수 있습니까? 접미사와 접미사 번호가 모두 포함 된 클래스를 만들어야합니까?
나는 그렇게 생각하지 않는다. 실제로 접미어를 정렬해야한다. 어쩌면 그는 V와 W (V는 확실하게)를 모두 분류 할 수도 있습니다. 이 신문은 너무 모호하고 불완전하기 때문에 저자 집에 폭탄을 던지고 싶습니다. – Erandros
OK, 아마도. 나는 W [i]의 접미어를 각 행 i의 키로 사용하여 W를 정렬하고 그 결과를 V에 저장하는 것을 의미했습니다. – Colin
아, 불완전하게 불행히도 학술 논문에서 흔히 볼 수 있습니다. – Colin