PHP 데이터 구조: Trie 트리를 사용하여 접두어 일치 문자를 효율적으로 찾습니다.

트리 트리는 접두사와 일치하는 문자를 효율적으로 찾는 데 사용되는 트리 데이터 구조입니다. 일련의 노드로 구성되며 각 노드는 문자를 나타냅니다. 문자열을 삽입하려면 루트 노드에서 시작하여 캐릭터의 경로를 따라 노드를 만들거나 찾습니다. 검색 시 문자별로 아래로 검색하여 일치하는 단어가 있는지 확인합니다. 이 경우 Trie 트리를 사용하여 동물 이름을 저장하고 특정 접두사로 시작하는 동물을 빠르게 찾습니다.

PHP 데이터 구조: Trie 트리를 사용하여 접두어 일치 문자를 효율적으로 찾습니다.

소개

Trie 트리는 문자열을 저장하고 빠른 접두어 일치 검색을 지원하는 데 특별히 사용되는 트리 데이터 구조입니다. 효율성과 공간 절약으로 잘 알려져 있으며 자연어 처리, 맞춤법 검사, 네트워크 라우팅 등의 분야에서 널리 사용됩니다.

트리 트리 구조

트리 트리는 일련의 노드로 구성되며 각 노드는 문자를 나타냅니다. 루트 노드부터 시작하여 트리의 각 수준은 문자열의 접두사를 나타냅니다. 각 노드에는 해당 접두사로 시작하는 다양한 접미사를 나타내는 여러 하위 노드가 있을 수 있습니다.

Insert

Trie 트리에 문자열을 삽입하려면 다음 단계를 수행하세요.

function insert(TrieNode $root, $string) {
    $node = $root;
    for ($i = 0; $i < strlen($string); $i++) {
        $char = $string[$i];
        if (!isset($node->children[$char])) {
            $node->children[$char] = new TrieNode();
        }
        $node = $node->children[$char];
    }
    $node->isWord = true;
}

Search

Trie 트리에 특정 문자열이 있는지 검색하려면 다음 단계를 수행하세요.

function search(TrieNode $root, $string) {
    $node = $root;
    for ($i = 0; $i < strlen($string); $i++) {
        $char = $string[$i];
        if (!isset($node->children[$char])) {
            return false;
        }
        $node = $node->children[$char];
    }
    return $node->isWord;
}

실제 사례

다음과 같이 동물 이름이 포함된 목록이 있다고 가정합니다.

$animals = ['dog', 'cat', 'rabbit', 'turtle', 'bird'];

이러한 동물 이름을 저장하기 위해 Trie 트리를 만듭니다.

$root = new TrieNode();
foreach ($animals as $animal) {
    insert($root, $animal);
}

이제 Trie 트리를 사용하여 접두사가 일치하는 동물을 쉽게 찾을 수 있습니다. 예를 들어, "d로 시작하는 동물"을 검색하면:

$prefix = 'd';
$result = [];
foreach ($animals as $animal) {
    if (search($root, $prefix . $animal)) {
        $result[] = $animal;
    }
}
print_r($result);

출력 결과는 다음과 같습니다:

Array
(
    [0] => dog
)

위 내용은 PHP 데이터 구조: Trie 트리를 사용하여 접두어 일치 문자를 효율적으로 찾습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!