php-word-filter/Trie.php at master · dww619/php-word-filter · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
<?php
/**
 * User: [email protected]
 * Date: 2017/8/29
 * Time: 上午10:56
 */

class Node
{
    public $value = null;
    public $children = array();
}


class Trie
{
    public $root;
    public $max_len;

    public function __construct()
    {
        $this->root = new Node();
        mb_internal_encoding("UTF-8");
    }


    public function insert($word)
    {
        $node =& $this->root;

        $word_len = mb_strlen($word);

        if ($word_len> $this->max_len) {
            $this->max_len = $word_len;
        }

        for ($i=0; $i<$word_len; $i++) {

            $char = mb_substr($word, $i, 1);

            if (!array_key_exists($char, $node->children)) {
                $child = new Node();
                $node->children[$char] = $child;
                $node =& $node->children[$char];

            } else {
                $node =& $node->children[$char];
            }
        }

        $node->value = $word;
    }


    public function load_words($file)
    {
        $handle = fopen($file, 'r');

        while (!feof($handle)) {
            $word = rtrim(fgets($handle));

            if (!empty($word)) {
                $this->insert($word);
            }
        }
    }


    public function search($word)
    {
        $node = $this->root;

        $word_len = mb_strlen($word);

        for ($i=0; $i<$word_len; $i++) {
            $char = mb_substr($word, $i, 1);

            if (!array_key_exists($char, $node->children)) {
                return $node->value;
            } else {
                $node = $node->children[$char];
            }
        }

        return $node->value;
    }


    public function search_all($text)
    {
        $result = array();

        $str_len = mb_strlen($text);

        for ($i = 0; $i <$str_len ; $i++) {

            $search_word = mb_substr($text, $i, $this->max_len);
            $filter_word = $this->search($search_word);
            if ($filter_word) {
                $result[] = $filter_word;
            }
        }

        return array_unique($result);
    }
}