algorithme de recherche php

Question

Un fichier contient 300 000 éléments de données ! Une donnée par ligne

Les mots des pairs ! Par exemple, les sommets post-stop sont des mots homologues
Comment trouver toutes les données qu'il contient

S'il vous plaît, donnez-moi quelques idées

Answer 1

Utilisez les commandes Linux pour remplir les conditions requises. Exemple

统计文件夹下包含Action( 数量
grep Action\( ~/www/pms/app/app/controllers/*.php | wc -l

Answer 2

Ma suggestion est d'écrire un algorithme de tri spécial, puis d'utiliser usort pour trier, de sorte que les mêmes mots soient triés ensemble, puis sortis dans l'ordre

La logique approximative de l'algorithme de tri est

int cmp($left, $right) {
   //如果长度都不一致，直接放弃
   if(strlen($left) != strlen($right))
       return strcmp($left, $right);
   //长度一致的，按照字符切分，统计，判断是否一致
   $arrleft = str_split($left);
   $arrright = str_split($right);
   $leftstat = array();
   $rightstat = array();
   foreach($arrleft as $char) {
        if(array_key_exists($char, $leftstat))
            $leftstat[$char]++;
        else
            $leftstat[$char]=0;
   }
   foreach($arrright as $char) {
        //逻辑类似
   }
   //比较两个数组的统计是否一致
   if(count(array_diff_assoc($leftstat, $rightstat)) == 0)
       return 0;
   else
       return strcmp($left, $right);
}

1. Pour trier 300 000 lignes de données, utilisez usort + la fonction cmp ci-dessus

2. Parcourez les données triées de la ligne 2 jusqu'à la fin et jugez si cette ligne est cohérente avec la ligne précédente Oui : sortie, non, descendez.

Probablement. Écrit à la main

Answer 3

<?php

/**
 * 建立 tries Tree，存储对应单词，减少存储量，加快检索速度
 * (T)代表是一个单词
 * (F)代表不是一个单词
 *
 * hi
 * his
 * is
 *     root
 *    /   \
 *  h (F)  i(F)
 *  |      |
 *  i (T)  s(T)
 *  |
 *  s (T)
 */
class TreeNode
{
    public $isStr;
    public $next;

    /**
     * TreeNode constructor.
     *
     * 字符串为 a-z 组成，所以可以直接将大小写字符，都存成小写
     * 0 - 26 对应 a - z
     */
    public function __construct()
    {
        $this->isStr = false;
        $this->next = [];
    }
}


///构建Tries Tree
class Helper
{
    public $treeRoot;

    public $debug = false;///此处开启是否以字符为索引

    public function __construct()
    {
        $this->treeRoot = new TreeNode();
    }

    /**
     * @param $str
     */
    public function insert($str)
    {
        $str = strtolower($str);///将所有的字符都作为小写存储

        $node = $this->treeRoot;
        for ($i = 0; $i < strlen($str); ++$i) {
            $index = $this->char2index($str{$i});
//            $index = $str{$i};
            if (empty($node->next[$index])) {
                $node->next[$index] = new TreeNode();
            }
            $node = $node->next[$index];
        }
        $node->isStr = true;
    }

    private function char2index($ch)
    {
        return ($this->debug) ? $ch : intval(ord($ch) - ord('a'));
    }

    private function index2char($index)
    {
        return ($this->debug) ? $index : chr($index + ord('a'));
    }

    /**
     * 查找对应的字符串的同形词
     * @param $str
     * @return array
     */
    public function find($str)
    {
        $result = [];

        $str = strtolower($str);///将所有的字符都作为小写存储

        $nextStr = ''; ///从后向前，逐渐追加字符，查找对应的数据
        for ($i = strlen($str) - 1; $i >= 0; --$i) {
            ///这里可以设置阈值，比如当需要找的字符串长度 > 2
            /// if(strlen($nextStr) < 2) continue;
            $nextStr = $str{$i} . $nextStr;

            $result = array_merge($result, $this->getResult($nextStr));
        }
        return array_unique($result);
    }

    /**
     * 找到对应字符串开头的所有单词
     * @param $str
     * @return array
     */
    private function getResult($str)
    {
        $result = [];
        $root = $this->treeRoot;

        ///先找到 tries 树中，对应的节点，确定节点是否包含子节点
        for ($i = 0; $i < strlen($str); ++$i) {
            if (empty($root)) {
                return $result;
            }
            $index = $this->char2index($str{$i});
            $root = $root->next[$index];
        }

        ///利用队列遍历Tries 树，实现 O(n) 检索
        $queue = new SplQueue();

        ///将节点，和字符起始点，记录到数据中，后续取用
        $next = ['node' => $root, 'str' => $str];
        $queue->push($next);

        while (!$queue->isEmpty()) {
            $next = $queue->pop();

            if ($next['node']->isStr) {///确定找到的是单词后，记录到结果集
                $result[] = $next['str'];
            }

            ///将下一个可能的结果集数组，放入到队列中查找
            if (!empty($next['node']->next)) {
                foreach ($next['node']->next as $index => $item) {
                    $next = ['node' => $item, 'str' => $next['str'] . $this->index2char($index)];
                    $queue->push($next);
                }
            }
        }
        return $result;
    }
}

$helper = new Helper();

$helper->insert("is");
$helper->insert("his");
$helper->insert("her");

$helper->insert('post');
$helper->insert('top');
$helper->insert('stop');


$result = $helper->find('post');
print_r($result);

$result = $helper->find('hi');
print_r($result);