php search algorithm

Question

A file has 300,000 pieces of data! One data per line

Peer words! For example, post stop tops are peer words
How do you find out all the data in it

Please give me some ideas

Answer 1

Use linux commands to complete your requirements. Example

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

Answer 2

My suggestion is to write a special sorting algorithm, and then use usort to sort, so that the same words are sorted together, and then output in order

The rough logic of the sorting algorithm is

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. To sort 300,000 rows of data, use usort + the above cmp function

2. Traverse the sorted data from row 2 to the end, and judge whether this row is consistent with the previous row. Yes: output, no, go down.

Probably. Written by hand

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