algoritma carian php

Question

Satu fail mempunyai 300,000 keping data! Satu data setiap baris

Kata sebaya! Contohnya, post stop tops ialah perkataan rakan sebaya
Bagaimana anda mengetahui semua data di dalamnya

Sila beri saya beberapa idea

Answer 1

Gunakan arahan linux untuk melengkapkan keperluan anda. Contoh

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

Answer 2

Cadangan saya ialah menulis algoritma pengisihan khas, dan kemudian gunakan usort untuk mengisih, supaya perkataan yang sama diisih bersama, dan kemudian keluarkan mengikut tertib

Logik kasar algoritma pengisihan ialah

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. Untuk mengisih 300,000 baris data, gunakan usort + fungsi cmp di atas

2. Lintas data yang diisih dari baris 2 hingga akhir, dan nilai sama ada baris ini konsisten dengan baris sebelumnya Ya: keluar, tidak, turun.

Mungkin. Ditulis dengan tangan

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