사전 구현에 가장 적합한 데이터 구조?

사전 구현에 가장 적합한 데이터 구조?

---

사전의 모든 단어를 저장하는 데 가장 적합한 데이터 구조는 무엇입니까? 내가 생각할 수있는 최선은 사용하는 것이었다 HashMapA를 매핑 할을 HashTable. 기본적으로 첫 번째 문자에 따라 연관을 얻은 HashTable다음이를 사용하여 해당 문자에서 시작하는 단어를 추가 할 수 있습니다. 그런 다음 문자열을 기반으로 좋은 해시 함수를 선택합니다.

더 나은 접근 방법이 있습니까?

---

수행하려는 작업에 따라 좋은 데이터 구조가 많이 있습니다.

단어를 저장하고 "이 단어가 여기에 있습니까?"라고 물 으려면 다른 멋진 기계가없는 표준 해시 테이블이 합리적인 접근 방식입니다. 해당 단어가 미리 고정 된 목록 인 경우 완벽한 해시 테이블 을 사용하여 뛰어난 성능과 공간 사용을 고려하십시오.

빠른 조회를 지원하면서 주어진 접두사가 존재하는지 확인할 수 있기를 원한다면 , 약간의 공간 비효율적 일 수 있지만 trie 는 좋은 옵션입니다. 또한 빠른 삽입 또는 삭제를 지원합니다. 또한 해싱이 제공하지 않는 알파벳 순서로 반복 할 수 있습니다. 이것은 본질적으로 답변에서 설명한 구조이지만 사용 사례에 따라 다른 시도 표현이 더 좋을 수 있습니다.

위의 것 외에도 단어 목록이 고정되어 있다는 사실을 알고 있는 경우 기본적으로 언어에 대한 최소 상태 DFA 인 DAWG (방향성 비순환 단어 그래프)를 사용하는 것이 좋습니다. trie보다 훨씬 작지만 동일한 작업을 많이 지원합니다.

트라이와 같은 동작을 원하지만 엄청난 공간 패널티를 지불하고 싶지 않다면 기수 트리 처럼 삼항 검색 트리 가 또 다른 실행 가능한 옵션 입니다 . 이것들은 매우 다른 구조이지만 다른 상황에서 트라이보다 훨씬 나을 수 있습니다.

공간이 문제이지만 트라이를 원한다면 간결한 트라이 표현을 살펴보십시오. 검색 속도는 느리지 만 이론적으로는 최적의 공간 사용량입니다. 링크는 방대한 양의 데이터를 전송하는 쉬운 방법으로 JavaScript에서 어떻게 사용되는지에 대해 설명합니다. 대체 간결한 표현은 double-array trie 이지만, 나는 그것에 대해 거의 알지 못합니다.

다른 단어와 유사한 단어를 찾아야하는 맞춤법 검사와 같은 작업에 사전을 사용하려는 경우 BK- 트리는 고려해야 할 훌륭한 데이터 구조입니다.

도움이 되었기를 바랍니다!

참고 URL : https://stackoverflow.com/questions/10017808/best-data-structure-for-implementing-a-dictionary