PHP implémente la fonction d'association de recherche (basée sur l'algorithme d'arborescence du dictionnaire)

La fonction d'association de recherche est une fonction de base des principaux moteurs de recherche.Comme le montre la figure ci-dessous, cette fonction simplifie le comportement de saisie de l'utilisateur et peut recommander des termes de recherche populaires aux utilisateurs. Parlons de la façon d'utiliser PHP pour implémenter la recherche. Fonctionnalités Lenovo.

Principe de mise en œuvre

La fonction d'association de recherche se décompose en deux parties

1 Compte tenu d'un. Mots de requête et trouvez d'autres mots de requête cibles préfixés avec

2. Triez les mots de requête cibles et sélectionnez plusieurs mots de requête avec un poids élevé

Cet article se concentrera sur l'explication de la mise en œuvre de la première partie utilise l'arbre de Trie, également appelé arbre de dictionnaire, cette structure de données pour résoudre ce problème. La chaîne cible préfixée par cette chaîne peut être trouvée facilement et rapidement via l'arborescence Trie.

Qu'est-ce qu'un arbre de Trie

L'arbre de Trie, également connu sous le nom d'arbre de dictionnaire, également connu sous le nom d'arbre de recherche de mots ou d'arbre de clés, est une structure arborescente et des variantes de hachage. d'arbre. Les applications typiques sont le comptage et le tri d'un grand nombre de chaînes (mais sans s'y limiter), elles sont donc souvent utilisées par les systèmes de moteurs de recherche pour les statistiques de fréquence des mots de texte. Ses avantages sont les suivants : minimiser les comparaisons de chaînes inutiles et l'efficacité des requêtes est souvent supérieure à celle des tables de hachage.

L'idée centrale de Trie est d'échanger de l'espace contre du temps. Utilisez le préfixe commun des chaînes pour réduire le temps de requête et améliorer l'efficacité.

Il a trois propriétés de base :

1. Le nœud racine ne contient pas de caractères, et chaque nœud à l'exception du nœud racine ne contient qu'un seul caractère.

2. Du nœud racine à un certain nœud, les caractères passant sur le chemin sont connectés pour former la chaîne correspondant au nœud.

3. Tous les nœuds enfants de chaque nœud contiennent des caractères différents.

Si nous avons la chaîne suivante

hello，hi，today，touch，weak

, alors l'arbre de Trie construit est comme indiqué ci-dessous

Lors de l'interrogation, juste par profondément en parcourant l'arborescence caractère par caractère en partant de la racine, vous pouvez trouver d'autres mots de requête préfixés par ce mot.

Implémentation du code

Il existe deux méthodes principales pour implémenter la fonction d'association de recherche :

1 Construisez l'ensemble de données de mots de requête dans un arbre Trie.

2. Recherchez tous les mots de requête préfixés par un certain mot de requête

Étape 1 : Construire l'arbre de Trie

Notez qu'en raison d'un seul caractère, il y a Chaînes chinoises et anglaises, utilisez donc le code suivant pour diviser chaque chaîne, convertissez la chaîne en un tableau de caractères

$charArray = preg_split(&#39;/(?<!^)(?!$)/u&#39;, $str);

, puis exécutez la méthode addWordToTrieTree sur chaque chaîne. Cette méthode ajoutera le mot au mot. Arbre de tri. La méthode récursive est utilisée ici

    public function buildTrieTree($strList) {
        $tree = [];
        foreach($strList as $str) {
            $charArray = preg_split(&#39;/(?<!^)(?!$)/u&#39;, $str); 
            $tree = $this->addWordToTrieTree($charArray, $tree);
        }
        return $tree;
    }
    public function addWordToTrieTree($charArray, $tree) {
        if (count($charArray) == 0) {
            return [];
        }
        $char = $charArray[0];
       
        $leftStr = array_slice($charArray, 1);
        $tree[$char] = $this->addWordToTrieTree($leftStr, $tree[$char]);
        
        return $tree;
    }

Étape 2 : Interroger le mot préfixe

Interroger le mot préfixe, c'est-à-dire, étant donné une chaîne, interroger toutes les chaînes. dans l'arborescence qui sont préfixées par cette chaîne se trouvent le processus d'association.

Appelez d'abord la méthode findSubTree pour trouver le sous-arbre où se trouve le préfixe à partir du Trie, puis appelez la méthode traverseTree pour parcourir le sous-arbre et extraire toutes les chaînes. La méthode récursive est également utilisée ici.

public function queryPrefix($prefix) {
        $charArray = preg_split(&#39;/(?<!^)(?!$)/u&#39;, $prefix);
        $subTree = $this->findSubTree($charArray, $this->tree);
        
        $words = $this->traverseTree($subTree);
        
        foreach($words as &$word) {
            $word = $prefix . $word;
        }
        return $words;
    }
    public function findSubTree($charArray, $tree) {
        foreach($charArray as $char) {
            if (in_array($char, array_keys($tree))) {
                $tree = $tree[$char];
            } else {
                return [];
            }
        }
        return $tree;
    }
    public function traverseTree($tree) {
        $words = [];
        foreach ($tree as $node => $subTree) {
            if (empty($subTree)) {
                $words[] = $node;
                return $words;
            }
            
            $chars = $this->traverseTree($subTree);
            foreach($chars as $char) {
                $words[] = $node . $char;
            }
        }
        return $words;
    }

Code et résultats des tests

Code complet :

tree = $this->buildTrieTree($strList);
    }
    public function queryPrefix($prefix) {
        $charArray = preg_split(&#39;/(?<!^)(?!$)/u&#39;, $prefix);
        $subTree = $this->findSubTree($charArray, $this->tree);
        
        $words = $this->traverseTree($subTree);
        
        foreach($words as &$word) {
            $word = $prefix . $word;
        }
        return $words;
    }
    public function findSubTree($charArray, $tree) {
        foreach($charArray as $char) {
            if (in_array($char, array_keys($tree))) {
                $tree = $tree[$char];
            } else {
                return [];
            }
        }
        return $tree;
    }
    public function traverseTree($tree) {
        $words = [];
        foreach ($tree as $node => $subTree) {
            if (empty($subTree)) {
                $words[] = $node;
                return $words;
            }
            
            $chars = $this->traverseTree($subTree);
            foreach($chars as $char) {
                $words[] = $node . $char;
            }
        }
        return $words;
    }
    /**
     * 将字符串的数组构建成Trie树
     *
     * @param [array] $strList
     * @return void
     */
    public function buildTrieTree($strList) {
        $tree = [];
        foreach($strList as $str) {
            $charArray = preg_split(&#39;/(?<!^)(?!$)/u&#39;, $str); 
            $tree = $this->addWordToTrieTree($charArray, $tree);
        }
        return $tree;
    }
    /**
     * 把一个词加入到Trie树中
     *
     * @param [type] $charArray
     * @param [type] $tree
     * @return void
     */
    public function addWordToTrieTree($charArray, $tree) {
        if (count($charArray) == 0) {
            return [];
        }
        $char = $charArray[0];
       
        $leftStr = array_slice($charArray, 1);
        $tree[$char] = $this->addWordToTrieTree($leftStr, $tree[$char]);
        
        return $tree;
    }
    public function getTree() {
        return $this->tree;
    }
}
$strList = ['春风十里','春天在哪里','一百万个可能','一千年以后','后来','后来的我们','春天里','后会无期'];
$trieTree = new TrieTree($strList);
print_r($trieTree->getTree());
$prefix = '春';
$queryRes = $trieTree->queryPrefix($prefix);
print_r($queryRes);

Convertir 'Spring Breeze Ten Miles', 'Où est le printemps', 'Un million de possibilités', 'Mille Années plus tard », « Plus tard », « Plus tard nous », « Au printemps », « Il n'y aura pas de temps plus tard », ces titres de chansons sont utilisés comme ensembles de données pour construire un arbre de Trie et le tester.

Vous pouvez voir les résultats de sortie suivants

Arbre de Trie :

Array
(
    [春] => Array
        (
            [风] => Array
                (
                    [十] => Array
                        (
                            [里] => Array
                                (
                                )
                        )
                )
            [天] => Array
                (
                    [在] => Array
                        (
                            [哪] => Array
                                (
                                    [里] => Array
                                        (
                                        )
                                )
                        )
                    [里] => Array
                        (
                        )
                )
        )
    [一] => Array
        (
            [百] => Array
                (
                    [万] => Array
                        (
                            [个] => Array
                                (
                                    [可] => Array
                                        (
                                            [能] => Array
                                                (
                                                )
                                        )
                                )
                        )
                )
            [千] => Array
                (
                    [年] => Array
                        (
                            [以] => Array
                                (
                                    [后] => Array
                                        (
                                        )
                                )
                        )
                )
        )
    [后] => Array
        (
            [来] => Array
                (
                    [的] => Array
                        (
                            [我] => Array
                                (
                                    [们] => Array
                                        (
                                        )
                                )
                        )
                )
            [会] => Array
                (
                    [无] => Array
                        (
                            [期] => Array
                                (
                                )
                        )
                )
        )
)

Interrogez la chaîne préfixée par "spring"

Array
(
    [0] => 春风十里
    [1] => 春天在哪里
    [2] => 春天里
)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!