php实现基于DFA算法的违禁词过滤的类

在实现文字过滤的算法中，DFA是唯一比较好的实现算法。DFA即Deterministic Finite Automaton，也就是确定有穷自动机，它是是通过event和当前的state得到下一个state，即event+state=nextstate。下图展示了其状态的转换

 在这幅图中大写字母（S、U、V、Q）都是状态，小写字母a、b为动作。通过上图我们可以看到如下关系

在实现敏感词过滤的算法中，我们必须要减少运算，而DFA在DFA算法中几乎没有什么计算，有的只是状态的转换。

<?php
header("Content-type:text/html; charset=utf-8");
class MyMap
{
    public $isEnd = 0;
    private $keySpace = [];
	public function get($key)
	{
		return isset($this->keySpace[$key]) ? $this->keySpace[$key] : null;
	}
	public function put($key, $value)
	{
        $this->keySpace[$key] = $value;
	}
	public function hasNext()
    {
        return !empty($this->keySpace);
    }
}
class MyFilter
{
	public $map = null;
	public function addWordToMap($word)
	{
		$len = mb_strlen($word);
		if (is_null($this->map)) {
			$map = new MyMap();
		} else {
			$map = $this->map;
		}
		$tmp = $map;
		for ($i = 0; $i < $len; $i++) {
			$nowWord = mb_substr($word, $i, 1);
			$nowMap = $map->get($nowWord);
			if (!is_null($nowMap)) {
				$map = $nowMap;
			} else {
				$newMap = new MyMap();
				$map->put($nowWord, $newMap);
				$map = $newMap;
			}
			if ($i == ($len - 1)) {
				$map->isEnd = 1;
			}
		}
		$this->map = $tmp;
	}
	//最大匹配(有问题)
	public function searchFromMap($string)
	{
		$len = mb_strlen($string);
		$tmp = $this->map;
		$map = $this->map;
		$str = '';
		$result = [];
		for ($i = 0; $i < $len; $i++) {
			$nowWord = mb_substr($string, $i, 1);
			$nowMap = $map->get($nowWord);
			if (!is_null($nowMap)) {
				$str .= $nowWord;
				if ($nowMap->isEnd) {
                    if (!in_array($str, $result)) {
                        array_push($result, $str);
                    }
					$str = '';
					$map = $tmp;
				} else {
					$map = $nowMap;
				}
			} else {
				if (!empty($str)) {
					$i--;
				}
				$str = '';
				$map = $tmp;
			}
		}
		return $result;
	}
	//左侧全量匹配
    public function leftFullSearch($string)
    {
        $len = mb_strlen($string);
        $tmp = $this->map;
        $map = $this->map;
        $str = '';
        $result = [];
        for ($i = 0; $i < $len; $i++) {
            $nowWord = mb_substr($string, $i, 1);
            $nowMap = $map->get($nowWord);
            if (!is_null($nowMap)) {
                $str .= $nowWord;
                if ($nowMap->isEnd) {
                    if (!in_array($str, $result)) {
                        array_push($result, $str);
                    }
                    if ($nowMap->hasNext()) {
                        $map = $nowMap;
                    } else {
                        $str = '';
                        $map = $tmp;
                    }
                } else {
                    $map = $nowMap;
                }
            } else {
                if (!empty($str)) {
                    $i--;
                }
                $str = '';
                $map = $tmp;
            }
        }
        return $result;
    }
    public function matchSearch($string)
    {
    }
}
$example = new MyFilter();
$example->addWordToMap('中国人');
$example->addWordToMap('中国男人');
$example->addWordToMap('中国女人');
$example->addWordToMap('中国男');
$example->addWordToMap('中国女');
$example->addWordToMap('中国');
$example->addWordToMap('男人');
$example->addWordToMap('女人');
$example->addWordToMap('男');
$example->addWordToMap('女');
$example->addWordToMap('人');
$str = '我是中国人,我爱中国,中国男人发送中国女人男到中国男人发送';
var_dump($example->searchFromMap($str));
//var_dump($example->map);
//var_dump($result);
var_dump($example->leftFullSearch($str));