PHP implementiert die Suchassoziationsfunktion (basierend auf dem Wörterbuchbaumalgorithmus)

Die Suchassoziationsfunktion ist eine Grundfunktion der wichtigsten Suchmaschinen. Wie in der Abbildung unten gezeigt, vereinfacht diese Funktion das Eingabeverhalten des Benutzers und kann Benutzern beliebte Suchbegriffe empfehlen. Lenovo-Funktionen.

Implementierungsprinzip

Die Suchassoziationsfunktion ist in zwei Teile unterteilt

1 Wörter und finden Sie andere Zielabfragewörter, denen das Präfix vorangestellt ist

2. Sortieren Sie die Zielabfragewörter und wählen Sie mehrere Abfragewörter mit hoher Gewichtung aus

Dieser Artikel konzentriert sich auf die Erläuterung der Verwendung der Implementierung des ersten Teils Trie-Baum, auch Wörterbuchbaum genannt, löst dieses Problem mit dieser Datenstruktur. Die Zielzeichenfolge, der diese Zeichenfolge vorangestellt ist, kann einfach und schnell über den Trie-Baum gefunden werden.

Was ist ein Trie-Baum?

Der Trie-Baum, auch Wörterbuchbaum genannt, auch Wortsuchbaum oder Schlüsselbaum genannt, ist eine Baumstruktur und eine Hash-Variante von Baum. Typische Anwendungen sind das Zählen und Sortieren einer großen Anzahl von Zeichenfolgen (aber nicht auf Zeichenfolgen beschränkt), daher werden sie häufig von Suchmaschinensystemen für Statistiken zur Worthäufigkeit von Texten verwendet. Seine Vorteile sind: Minimierung unnötiger Zeichenfolgenvergleiche und häufig höhere Abfrageeffizienz als bei Hash-Tabellen.

Die Kernidee von Trie ist der Austausch von Raum gegen Zeit. Nutzen Sie das gemeinsame Präfix von Zeichenfolgen, um den Zeitaufwand für Abfragen zu reduzieren und die Effizienz zu verbessern.

Es hat drei grundlegende Eigenschaften:

1. Der Wurzelknoten enthält keine Zeichen und jeder Knoten außer dem Wurzelknoten enthält nur ein Zeichen.

2. Vom Wurzelknoten bis zu einem bestimmten Knoten werden die auf dem Pfad durchlaufenden Zeichen verbunden, um die dem Knoten entsprechende Zeichenfolge zu bilden.

3. Alle untergeordneten Knoten jedes Knotens enthalten unterschiedliche Zeichen.

Wenn wir die folgende Zeichenfolge

hello，hi，today，touch，weak

haben, dann sieht der konstruierte Trie-Baum wie unten gezeigt aus

Bei der Abfrage einfach By deep Wenn Sie den Baum Zeichen für Zeichen ausgehend von der Wurzel durchgehen, können Sie andere Suchwörter finden, denen dieses Wort vorangestellt ist.

Code-Implementierung

Es gibt zwei Kernmethoden zum Implementieren der Suchassoziationsfunktion:

1. Konstruieren Sie den Abfragewortdatensatz in einen Trie-Baum

2. Finden Sie alle Abfragewörter, denen ein bestimmtes Abfragewort vorangestellt ist

Schritt 1: Trie-Baum erstellen

Beachten Sie, dass aufgrund eines Zeichens Es gibt Verwenden Sie also den folgenden Code, um jede Zeichenfolge aufzuteilen, konvertieren Sie die Zeichenfolge in ein Array von Zeichen

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

und führen Sie dann die Methode addWordToTrieTree für jede Zeichenfolge aus. Diese Methode wird dem Trie hinzugefügt Hier wird die rekursive Methode verwendet

    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;
    }

Schritt 2: Präfixwort abfragen

Präfixwort abfragen, d. h. bei gegebener Zeichenfolge alle Zeichenfolgen abfragen Die Bäume, denen diese Zeichenfolge vorangestellt ist, sind der Prozess der Assoziation.

Rufen Sie zuerst die Methode findSubTree auf, um den Teilbaum zu finden, in dem sich das Präfix im Trie befindet, und rufen Sie dann die Methode traverseTree auf, um den Teilbaum zu durchlaufen und alle Zeichenfolgen zu extrahieren.

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 und Testergebnisse

Vollständiger Code:

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);

Konvertieren Sie „Spring Breeze Ten Miles“, „Where is Spring“, „A Million Possibilities“, „A Thousand“. „Years later“, „Later“, „Later us“, „In the spring“, „There will be no time later“ – diese Songtitel werden als Datensätze verwendet, um einen Trie-Baum zu erstellen und zu testen.

Sie können die folgenden Ausgabeergebnisse sehen

Trie-Baum:

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
                                (
                                )
                        )
                )
        )
)

Fragen Sie die Zeichenfolge mit dem Präfix „spring“ ab

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

Das obige ist der detaillierte Inhalt vonPHP implementiert die Suchassoziationsfunktion (basierend auf dem Wörterbuchbaumalgorithmus). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!