AC算法实现非标准地址匹配-PHP实现
一般完整的地址包括 xx省xx市xx县(区)，可以用关键字(省|市|县)切割，而非标准地址可能是直接省略一些关键字，比如 广东广州天河区xx街道303号 ，还有一些直接没有写省级，直接从市开始，比如 广州天河xx街道123号，这种非标准的地址，普通字符串处理方式很难解析出省市区，而使用AC算法则可以很方便解析出来
PHP的AC算法实现参考：AC算法-PHP实现
定义地区表
create table area (
id bigint not null comment '地区编号',
parent_id bigint default null comment '父级地区编号',
cname varchar(100) comment '名称',
ctype int comment '类型：1-省，2-市，3-区(县)'
)
下面代码基于thinkphp框架编写，用到了一些框架提供的函数，比如构造函数中的 M 函数查询数据库
AddressParserLogic类在创建实例时，会从数据库中加载所有省市区，创建前缀树(状态机)，调用方使用时，只需要调用parse方法即可解析
由于每次加载一次数据库中的省市区还是挺耗时的，所以做成单例模式，避免不必要的开销
<?php
/**
* 非标准的地址解析出省市县
* Author: keyuan.xie
* Date: 2021/6/17
* Time: 11:19
*/
namespace Common\Logic;
include_once APP_PATH . "Common/Library/AC.php";
class AddressParserLogic {
private static $instance = null;
private $addressMap;
private $trie;
private function __construct() {
// 从数据库中查出所有地区，用来构建状态机
$this->addressMap = M("area")->getField("id, parent_id, cname, ctype", true);
}
// 获取实例
public static function getInstance() {
if (is_null(AddressParserLogic::$instance)) {
$instance = new AddressParserLogic();
$instance->initAc();
AddressParserLogic::$instance = $instance;
}
return AddressParserLogic::$instance;
}
/**
* 传入数据初始化自动机
*/
private function initAc() {
// 将每个地址放入AC自动机
$this->trie = new \AC\Trie();
foreach ($this->addressMap as $id => $addressInfo) {
// 放入自动机
$nodeData = $this->trie->getNodeData($addressInfo["cname"]);
if (!is_null($nodeData)) {
$nodeData->data["list"][] = $addressInfo;
} else {
$this->trie->addWord($addressInfo["cname"], ["cname"=>$addressInfo["cname"], "list"=>[$addressInfo]]);
}
// 如果是省或市，并且名字含有“省”或“市”，则将它去掉“省”或“市”，再次放入自动机
if (in_array($addressInfo["ctype"], [1,2,3]) && preg_match("/(市|省|区|县)$/", $addressInfo["cname"])) {
$tmpName = mb_substr($addressInfo["cname"], 0, mb_strlen($addressInfo["cname"]) - 1);
$nodeData = $this->trie->getNodeData($tmpName);
if (!is_null($nodeData)) {
$nodeData->data["list"][] = $addressInfo;
} else {
$this->trie->addWord($tmpName, ["cname"=>$tmpName, "list"=>[$addressInfo]]);
}
}
}
$this->trie->makeAutomation();
}
/**
* 解析地址
* @param string $address 地址
* @return array 返回省市区的信息以及详细地址[province=>[], city=>[], region=>[], address=>""]
*/
public function parse($address) {
// province、city、region的内部结构就是data51数据库大area表的字段结构
$result = [
"province" => [], // 省
"city" => [], // 市
"region" => [], // 区
"address" => "", // 详细地址
];
$tmpTrieResult = $this->trie->match($address);
if (empty($tmpTrieResult)) {
$result["address"] = $address;
return $result;
}
// 把start_index相同的结果，用后一个代替
$prePos = $tmpTrieResult[0]["start_index"];
$preValue = $tmpTrieResult[0];
$trieResult = [];
for ($i = 1; $i < count($tmpTrieResult); $i++) {
if ($tmpTrieResult[$i]["start_index"] == $prePos) {
$preValue = $tmpTrieResult[$i];
} else {
$trieResult[] = $preValue;
$preValue = $tmpTrieResult[$i];
$prePos = $tmpTrieResult[$i]["start_index"];
}
}
$trieResult[] = $preValue;
// 从大到小
$currentType = 0;
$endIndex = 0;
foreach ($trieResult as $k => $res) {
if ($currentType === 3) { // 省市区都找完了，则退出循环
break;
}
$list = $res["data"]["list"];
$isOk = false;
// 还没找到省，则找省
if ($currentType < 1) {
for ($i = 0; $i < count($list); $i++) {
if ($list[$i]["ctype"] == 1) {
$result["province"] = $list[$i];
$currentType = 1;
$isOk = true;
break;
}
}
}
if ($isOk) {
$endIndex = $res["start_index"] + mb_strlen($res["data"]["cname"]);
continue;
}
// 还没找到市，则找市
if ($currentType < 2) {
$alternative = [];
for ($i = 0; $i < count($list); $i++) {
if ($list[$i]["ctype"] == 2) {
$alternative[] = $list[$i];
}
}
if (!empty($alternative)) {
// 有省份了，则查看哪个备选的市的上级是当前省份
if ($currentType == 1) {
for ($i = 0; $i < count($alternative); $i++) {
if ($alternative[$i]["parent_id"] == $result["province"]["id"]) {
$result["city"] = $alternative[$i];
$currentType = 2;
$isOk = true;
break;
}
}
} else { // 还没找到市，则去备选市的第一个
$result["city"] = $alternative[0];
$currentType = 2;
$isOk = true;
}
}
}
if ($isOk) {
$endIndex = $res["start_index"] + mb_strlen($res["data"]["cname"]);
continue;
}
// 还没找到区，则找区
if ($currentType < 3) {
$alternative = [];
for ($i = 0; $i < count($list); $i++) {
if ($list[$i]["ctype"] == 3) {
$alternative[] = $list[$i];
}
}
if (!empty($alternative)) {
// 有市了，则找哪个备选的区的上级是当前市
if ($currentType == 2) {
for ($i = 0; $i < count($alternative); $i++) {
if ($alternative[$i]["parent_id"] == $result["city"]["id"]) {
$result["region"] = $alternative[$i];
$currentType = 3;
$isOk = true;
break;
}
}
} else if ($currentType == 1) { // 有省，没有市，则找哪个区的id的前两位是等于当前省份id的前两位的
$provinceId2 = substr($result["province"]["id"], 0, 2);
for ($i = 0; $i < count($alternative); $i++) {
if ($provinceId2 == substr($alternative[$i]["id"], 0, 2)) {
$result["region"] = $alternative[$i];
$currentType = 3;
$isOk = true;
break;
}
}
} else { // 省市都没有，则取备选的第一个
$result["region"] = $alternative[0];
$currentType = 3;
$isOk = true;
}
}
}
if ($isOk) {
$endIndex = $res["start_index"] + mb_strlen($res["data"]["cname"]);
continue;
}
}
// 将详细地址填上
$result["address"] = mb_substr($address, $endIndex);
// 省市有缺失的，尝试补上
if (empty($result["province"])) { // 没有省
if (!empty($result["city"])) {
$provinceId = $result["city"]["parent_id"];
if (isset($this->addressMap[$provinceId])) {
$result["province"] = $this->addressMap[$provinceId];
}
} else if (!empty($result["region"])) {
$provinceId = substr($result["region"]["id"], 0, 2) . "0000";
if (isset($this->addressMap[$provinceId])) {
$result["province"] = $this->addressMap[$provinceId];
}
}
}
if (empty($result["city"])) { // 没有市
if (!empty($result["region"])) {
$cityId = $result["region"]["parent_id"];
if (isset($this->addressMap[$cityId])) {
$result["city"] = $this->addressMap[$cityId];
}
} else if (!empty($result["province"])) { // 有省，试试这个省是不是直辖市
$provinceName = $result["province"]["cname"];
$provinceId2 = substr($result["province"]["id"], 0, 2);
$isOk = false;
foreach ($trieResult as $res) {
if (strcmp($res["data"]["cname"], $provinceName) === 0) {
foreach ($res["data"]["list"] as $t) {
if ($t["ctype"] == 2 && $provinceId2 == substr($t["id"], 0, 2)) { // 是市，并且它id的前两位等于当前省id的前两位，则匹配成功
$result["city"] = $t;
$isOk = true;
}
if ($isOk) {
break;
}
}
}
if ($isOk) {
break;
}
}
}
}
return $result;
}
}
使用
$parser = AddressParserLogic::getInstance();
$parser->parse("广东广州天河棠下102路103号");
本文是原创文章，采用 CC 4.0 BY-SA 协议，完整转载请注明来自 KK元空间
阅读建议
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果