Patricia Trie IPv4 주소 및 위성 데이터의 빠른 검색을위한 Trie

Question

IP 주소 (모든 IPv4) 가보고 빠른 방법으로 보관할 수있는 C ++에서 프로그램을 작성하고 있습니다. 모든 IP 주소에는 데이터와 관련된 데이터가 있습니다. TRIE에 이미 있으면 TRIE의 IP 주소의 데이터를 새 주소 데이터와 병합하려고합니다. 존재하지 않으면 TRIE에 새 항목으로 추가하려고합니다. IP 주소 삭제는 필요하지 않습니다.

이를 구현하기 위해서는 Patricia Trie를 설계해야합니다. 그러나이 디자인을 초과하여 디자인을 시각화 할 수 없습니다. 그것은 나에게 꽤 순진한 것처럼 보이지만, 내 마음에 오는 유일한 아이디어는 IP 주소를 바이너리 양식으로 변경 한 다음 Trie를 사용하는 것이 었습니다. 그러나 나는 을 정확하게 이것을 정확하게 구현하는 것에 대해

나는 이것을 도울 수 있다면 정말 당신에게 감사 할 것입니다. 비슷한 질문을 찾았습니다 여기 질문이나 특히 대답은 CPAN 웹 사이트의 코드가 나에게 충분히 분명하지 않기 때문에 내 이해를 초과했습니다.

또한 내 데이터는 다음 형식입니다

10.10.100.1 : "Tom", "잭", "Smith"

192.168.12.12 : "Jones", "Liz"

12.124.2.1 : "지미", "조지"

10.10.100.1 : "Mike", "Harry", "Jennifer"

Answer 1

Patricia는 주어진 IP 주소에 대한 최상의 덮개 접두사를 찾는 문제를 해결합니다 (라우터가 192.168.0.0/16이 192.168.14.63에서 192.168.14.63에 가장 적합한 선택 사항이 선택됩니다).IP 주소를 정확히 일치 시키려고하는 경우 해시 테이블이 더 나은 선택입니다.

Answer 2

rhincheree 를 참조한다고 생각합니다.나는 radixtrie in Java에서 실제 키를 가치있는 키를 사용하는 시작점으로 사용하려는 경우. Patriciatrie <./ a> 그것은 백업 구조로서.

예제 다음 문자열을 사용하여

1. 10.10.101.2
2. 10.10.100.1
3. 10.10.110.3

트리 예제 (비 압축)

└── 1
    └── 0
        └── .
            └── 1
                └── 0
                    └── .
                        └── 1
                            ├── 0
                            │   ├── 1
                            │   │   └── .
                            │   │       └── (2) 10.10.101.2
                            │   └── 0
                            │       └── .
                            │           └── (1) 10.10.100.1
                            └── 1
                                └── 0
                                    └── .
                                        └── (3) 10.10.110.3

.

patricia trie (압축)

└── [black] 10.10.1
    ├── [black] 0
    │   ├── [white] (0.1) 00.1
    │   └── [white] (1.2) 01.2
    └── [white] (10.3) 10.10.110.3

.