> 백엔드 개발 > PHP 튜토리얼 > PHP는 불법 단어 필터링을 구현합니다(알고리즘 분석).

PHP는 불법 단어 필터링을 구현합니다(알고리즘 분석).

藏色散人
풀어 주다: 2023-04-11 08:04:02
앞으로
3307명이 탐색했습니다.

알고리즘 소개 键 키워드로 인해 트리가 생성되고 각 단어가 노드가 됩니다. 필터링이 필요한 문장을 순회하고, 트리에 있는 문장의 각 단어를 검색하여 존재하는지 확인하세요.

구현의 어려움

트리를 구성하는 것은 간단합니다. 중요한 점은 php에서 문자열을 순회하려면 단일 문자의 길이를 정확하게 얻어야 한다는 것입니다.
단순히 문자열을 순회하는 방법은 다음과 같습니다.

1

2

3

4

$strLen = mb_strlen($str);

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

    echo mb_substr($str, $i, 1, "utf8"),PHP_EOL;

}

로그인 후 복사
이 방법은 mb_* 일련의 함수를 사용하여 각 문자를 올바르게 가로채는 방법입니다. 많은 수를 처리할 때 속도가 매우 느립니다. 내 추측은 다음과 같습니다. mb_substr문자가 가로채질 때마다 문자열 앞의 문자 수를 계산해야 합니다.
문자열을 탐색하는 올바른 방법은 utf8의 인코딩 규칙에 따라 문자열을 가로채는 것입니다. 자세한 내용은 아래를 참조하세요.

php中遍历字符串需要自己正确的得到单个字符的长度。
简单遍历字符串的方法如下:

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

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

<?php

/**

 * 非法关键词检查

 */

class SensitiveWords

{

    protected $tree = null;

    protected $callIsNumeric = true;

    /**

     * 非法词汇列表,一个非法词汇占用一行

     */

    public function __construct($path = __DIR__ . &#39;/sensitiveWords.txt&#39;)

    {

        $this->tree = new WordNode();

        $file = fopen($path, "r");

        while (!feof($file)) {

            $words = trim(fgets($file));

            if ($words == &#39;&#39;) {

                continue;

            }

            //存在纯数字的非法词汇

            if (is_numeric($words)) {

                $this->callIsNumeric = false;

            }

            $this->setTree($words);

        }

        fclose($file);

    }

 

    protected function setTree($words)

    {

        $array = $this->strToArr($words);

        $tree = $this->tree;

        $l = count($array) - 1;

        foreach ($array as $k => $item) {

            $tree = $tree->getChildAlways($item);

            if ($l == $k) {

                $tree->end = true;

            }

        }

    }

 

    /**

     * 返回包含的非法词汇

     * @param string $str

     * @return array

     */

    public function check($str)

    {

        //先压缩字符串

        $str = trim(str_replace([&#39; &#39;, "\n", "\r"], [&#39;&#39;, &#39;&#39;, &#39;&#39;], $str));

        $ret = [];

        loop:

        $strLen = strlen($str);

        if ($strLen === 0) {

            return array_unique($ret);

        }

        //非法词汇中没有纯数字的非法词汇,待检测字符串又是纯数字的,则跳过不再检查

        if ($this->callIsNumeric && is_numeric($str)) {

            return array_unique($ret);

        }

        //挨个字符进行判断

        $tree = $this->tree;

        $words = &#39;&#39;;

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

            //unicode范围 --> ord 范围

            //一字节 0-127 --> 0 - 127

            //二字节 128-2047 --> 194 - 223

            //三字节 2048-65535 --> 224 - 239

            //四字节 65536-1114111 --> 240 - 244

            //@see http://shouce.jb51.net/gopl-zh/ch3/ch3-05.html

            $ord = ord($str[$i]);

            if ($ord <= 127) {

                $word = $str[$i];

            } elseif ($ord <= 223) {

                $word = $str[$i] . $str[$i + 1];

                $i += 1;

            } elseif ($ord <= 239) {

                $word = $str[$i] . $str[$i + 1] . $str[$i + 2];

                $i += 2;

            } elseif ($ord <= 244) {

                //四字节

                $word = $str[$i] . $str[$i + 1] . $str[$i + 2] . $str[$i + 3];

                $i += 3;

            } else {

                //五字节php都溢出了

                //Parse error: Invalid UTF-8 codepoint escape sequence: Codepoint too large

                continue;

            }

            //判断当前字符

            $tree = $tree->getChild($word);

            if (is_null($tree)) {

                //当前字不存在,则截取后再次循环

                $str = substr($str, $i + 1);

                goto loop;

            } else {

                $words .= $word;

                if ($tree->end) {

                    $ret[] = $words;

                }

            }

        }

        return array_unique($ret);

    }

 

    protected function strToArr($str)

    {

        $array = [];

        $strLen = mb_strlen($str);

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

            $array[] = mb_substr($str, $i, 1, "utf8");

        }

        return $array;

    }

}

/**

 * 单个字符的节点

 */

class WordNode

{

    //是否为非法词汇末级节点

    public $end = false;

    //子节点

    protected $child = [];

 

    /**

     * @param string $word

     * @return WordNode

     */

    public function getChildAlways($word)

    {

        if (!isset($this->child[$word])) {

            $this->child[$word] = new self();

        }

        return $this->child[$word];

    }

 

    /**

     * @param string $word

     * @return WordNode|null

     */

    public function getChild($word)

    {

        if ($word === &#39;&#39;) {

            return null;

        }

        if (isset($this->child[$word])) {

            return $this->child[$word];

        }

        return null;

    }

}

로그인 후 복사

该方法是利用mb_*系列函数来正确截取每个字符,处理大量字符串时速度非常慢,我猜测是:mb_substr每截取一个字符,都要计算该字符串之前,有多少个字符。
正确的遍历字符串的方式是按utf8

알고리즘 구현

rrreee추천 학습: "PHP 비디오 튜토리얼

"

위 내용은 PHP는 불법 단어 필터링을 구현합니다(알고리즘 분석).의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

관련 라벨:
php
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿