Patricia Trie에서 가장 긴 접두사 검색을 찾기위한 알고리즘/단계

Question

IP 접두사 조회를 위해 Patricia Tries를 구현하고 있습니다. 전체 키 일치를 위해 코드가 작동하지만 접두사 검색 문제에 직면 할 수 있습니다.

1.2.3.0
1.2.0.0

위의 경우 접두사 검색 알고리즘을 도와 줄 수 있습니까?이를 별도의 길이 (예 : /24 및 16)의 키로 간주해야합니까?

Answer 1

Net-Patricia를 살펴보십시오. 이것은 IP 주소를 찾기 위해 Patricia Trie의 구현입니다. 인터페이스는 PERL이지만 기본 코드는 C에 있습니다. 여기에는 링크가 있지만 많은 CPAN 아카이브가 다음을 가져야합니다.

http://cpansearch.perl.org/src/philipp/net-patricia-1.15_07/libpatricia/patricia.c

Answer 2

이 트리를 고정 길이의 요소로 저장하는 데이 트리를 사용하는 경우 확실히 올바른 방법이 아닙니다. 여기서 요점은 PT가 가변 길이 데이터를 저장하는 데 특히 유용하다는 것입니다.

IP 번호의 일부를 가변 길이의 접두사로 저장하는 경우 PT가 좋은 선택입니다.
이 경우 예, 키는 길이가 다르아야합니다.
바이너리 0xc0 0xa8에 "192.168"접두사 "192.168"을 저장한다고 가정 해 봅시다.이를 첫 번째 키로 추가합니다.
그런 다음 192.168.1.1과 같은 IP를 검색 할 때 TRIE에 192.168이 포함 된 정보를 얻을 수 있습니다.

당신이해야 할 일은 트리를 가로 지르는 동안 "공통 부분"을 저장하는 것입니다.
이것은 사소한 추가입니다 이것 구현. 트리를 내려 가면서 재귀 함수의 매개 변수 어딘가에 공통 부분을 저장하는지 확인하십시오.
Patricia Trie를 잘 이해하려면 독서를 제안합니다 Robert Sedgewick의 알고리즘 책 이것은 훌륭한 지식의 원천입니다.

편집하다: pt에 C 줄을 저장할 때 한 가지 문제가 있습니다. 이 트리는 이진 데이터를 저장하도록 설계되었지만 전체 바이트를 얻는 데 관심이 있습니다. 비트 크기의 크기가 8 인 경우에만 접두사의 공통 부분을 저장하고 있는지 확인하십시오. 잘못된 예 : 트리에 키가 있습니다 : 0xc0 0xa5는 0xc0 0xa6에서 보이고 있습니다. 공통 부분 "0xc0 0xa"가있을 때 횡단이 중지되지만 "0xc0"만 복용하는 데 관심이 있습니다. 따라서 비트가 아닌 공통 바이트를 저장하십시오.

Answer 3

LLVM의 테스트 코드에는 상당히 읽을 수있는 C 구현이 있습니다. https://llvm.org/svn/llvm-project/test-suite/trunk/multisource/benchmarks/mibench/network-patricia/