位置: IT常识 - 正文

Darts, 双数组Trie 文字处理技术 STPDomain Powered by Discuz!(双重数组)

编辑:rootadmin
Darts, 双数组Trie - 文字处理技术 - STPDomain - Powered by Discuz!Darts, 双数组Trie - 文字处理技术 - STPDomain - Powere

推荐整理分享Darts, 双数组Trie 文字处理技术 STPDomain Powered by Discuz!(双重数组),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:双数组trie树,双数组trie算法解析,dart多维数组,双数组排序,双数组排序,dart 二维数组,双数组数据结构,双数组数据结构,内容如对您有帮助,希望把文章链接给更多的朋友!

Darts, 双数组Trie - 文字处理技术 - STPDomain - Powered by Discuz!

2011-05-19|阅:118转:0|分享腾讯空间人人网开心网新浪微博腾讯微博搜狐空间推荐给朋友举报

双数组trie树的基本构造及简单优化

一、 基本构造

Trie树是搜索树的一种,来自英文单词"Retrieval"的简写,可以建立有效的数据检索组织结构,是中文匹配分词算法中词典的一种常见实现。它本 质上是一个确定的有限状态自动机(DFA),每个节点代表自动机的一个状态。在词典中这此状态包括"词前缀","已成词"等。

双 数组Trie(Double-Array Trie)是trie树的一个简单而有效的实现,由两个整数数组构成,一个是base[],另一个是check[]。设数组下标为i ,如果base,check均为0,表示该位置为空。如果base为负值,表示该状态为词语。Check表示该状态的前一状态,t=base+a, check[t]=i 。

复制代码

下 面举例(源自<<双数组Trie(Double-Array Trie)的数据结构与具体实现>>)来说明用双数组Trie(Double-Array Trie)构造分词算法词典的过程。假定词表中只有“啊,阿根廷,阿胶,阿拉伯,阿拉伯人,埃及”这几个词,用Trie树可以表示为:

我 们首先对词表中所有出现的10个汉字进行编码:啊-1,阿-2,唉-3,根-4,胶-5,拉-6,及-7,廷-8,伯-9,人-10。。对于每一个汉字, 需要确定一个base值,使得对于所有以该汉字开头的词,在双数组中都能放下。例如,现在要确定“阿”字的base值,假设以“阿”开头的词的第二个字序 列码依次为a1,a2,a3……an,我们必须找到一个值i,使得 base[i+a1],check[i+a1],base[i+a2],check[i+a2]……base[i+an],check[i+an]均为 0。一旦找到了这个i,“阿”的base值就确定为i。用这种方法构建双数组Trie(Double-Array Trie),经过四次遍历,将所有的词语放入双数组中,然后还要遍历一遍词表,修改base值。因为我们用负的base值表示该位置为词语。如果状态i对 应某一个词,而且Base=0,那么令Base=(-1)*i,如果Base的值不是0,那么令Base=(-1)*Base。得到双数组如下:

复制代码下标 1234567891011121314Base-14400004-94-11-12-4-14Check0000000222381013词缀啊阿埃阿根阿胶阿拉埃及阿根廷阿拉伯阿拉伯人用 上述方法生成的双数组,将“啊”,“阿”,“埃”,“阿根”,“阿拉”,“阿胶”,“埃及”,“阿拉伯”,“阿拉伯人”,“阿根廷”均视为状态。每个状态 均对应于数组的一个下标。例如设“阿根”的下标为i=8,那么check的内容是“阿”的下标,而base是“阿根廷”的下标的基值。“廷”的序列码为 x=8,那么“阿根廷”的下标为base+x=base[8]+8=12。

复制代码

二、 基本操作与存在问题

1, 查询

trie树的查询过程其实就是一个DFA的 状态转移过程,在双数组中实现起来比较简单:只需按照状态标志进行状态转移即可.例如查询“阿根廷”,先根据“阿”的序列码b=2,找到状态“阿”的下标 2,再根据“根”的序列码d=4找到“阿根”的下标base+d=8,同时根据check[base+d]=b,表明“阿根”是某个词的一部分,可以继续 查询。然后再找到状态“阿根廷”。它的下标为y=12,此时base[y]<0,check[y]=base+d=8,表明“阿根廷”在词表中,查 询完毕。Darts, 双数组Trie  文字处理技术  STPDomain  Powered by Discuz!(双重数组)

复制代码

查询过程中我们可以看到,对于一个词语的查询时间是只与它的长度相关的,也就是说它的时间复杂度为O(1).在汉语中,词语以单字词,双字词居多,超过三字的词语少之又少.因此,用双数组构建的trie树词典查询是理论上中文机械分词中的最快实现。

2, 插入与删除 双数组的缺点在于:构造调整过程中,每个状态都依赖于其他状态,所以当在词典中插入或删除词语的时候,往往需要对双数组结构进行全局调整,灵活性能较差。

将一个词语插入原有的双数组trie树中,相当于对DFA增加一个状态。首先我们应根据查询方法找出该状态本应所处的位置,如果该位置为空,那好办,直接 插入即可。如果该位置不为空。那么我们只好按照构造时一样的方法重新扫描得出该状态已存在的最大前缀状态的BASE值,并由此依次得出该状态后继结点的 BASE值。在这其中还要注意CHECK值的相应变化。

例如说,如果"阿拉根"某一天也成为了一个词,我们要在trie树中插入这一状态。按计算它的位置应在8,但8是一个已成状态.所以我们得重新确定"阿 拉"这一最大已成前缀状态的BASE值.重新扫描得出BASE[10]=11。这样状态15为"阿拉根",且BASE[15]为负(成 词),CHECK[15]=10;状态20为"阿拉佰",且BASE[20]=-4,CHECK=10。

这样的处理其实是非常耗时间的,因为得依次对每一个可能BASE值进行扫描来进行确定最大已成前缀状态的BASE值。这个确定过程在构造时还是基本可以忍 受的,毕竟你就算用上一,两天来构造也没有问题(只要你构造完后可以在效运行即可)。但在插入比较频繁时,如果每次都需要那么长的运行时间,那确实是无法 忍受的。

双数组删除实现比较简单,只需要将删除词语的对应状态设为空即可――即BASE值,CHECK均为设0。但它存在存在一个空间效率的问题.例如,当我们在 上面删除"埃及"这一词语时,状态11被设为空。而状态10则成了一个无用结点――它不成词,而且在插入新词时也不可重用。所以,随着删除的进行,空状态 点和无用状态点不断增多,空间的利用率会不断的降低。

三、 简单优化

优化的基本思路是将双数组trie树构建为一种动态检索方法,从而解决插入和删除所存在的问题。

1, 插入优化 在插入需要确定新的BASE值时,我们是只需要遍历空状态的。非空状态的出现意味着某个BASE值尝试的打败,我们可以完全不必理会。所以,我们可以对所有的空状态构建一个序列,在确定BASE值时只需要扫描该序列即可。 对双数组中的空状态的递增结点r1,r2, …, rm,我们可以这样构建这一空序列: CHECK[ri]=?ri+1 (1 i m?1), CHECK[rm]=?(DA_SIZE+1) 其中r1= E_HEAD,为第一个空值状态对应的索引点。这样我们在确定BASE值时只需扫描这一序列即可。这样就省去了对非空状态的访问时间。

这种方法在空状态并不太多的情况下可以很大程度的提高插入速度。

2, 删除优化 1) 无用结点 对于删除叶结点时产生的无用结点,可以通过依次判断将它们置为空,使得可在插入新词时得以重用。例如,如果我们删除了上例中的"阿根廷",可以看到"阿根"这一状态没有子状态,因此也可将它置为空。而"阿"这一状态不能置空,因为它还有两个子状态。

2) 数组长度的压缩 在删除了一个状态后,数组末尾可能出现的连续空状态我们是可以直接删除的。另外我们还可以重新为最大非空索引点的状态重新确定BASE值,因为它有可能已经由于删除的进行而变小。这们我们可能又得以删除一些空值状态。

本文链接地址:https://www.jiuchutong.com/zhishi/310290.html 转载请保留说明!

上一篇:WordPress 去掉留言中的网址字段(wordpress如何删除导入的主题)

下一篇:WordPress配置谷歌分析(Google Analytics)和Search Console(GSC)教程(wordpress部署到github)

  • IQOO如何关闭锁屏原子随身听(iQOO如何关闭锁屏壁纸的锁屏)

    IQOO如何关闭锁屏原子随身听(iQOO如何关闭锁屏壁纸的锁屏)

  • 从微信转到支付宝怎么转(从微信转到支付宝怎么转没有银行卡)

    从微信转到支付宝怎么转(从微信转到支付宝怎么转没有银行卡)

  • 苹果13pro怎么关闭定位(苹果13pro怎么关机)

    苹果13pro怎么关闭定位(苹果13pro怎么关机)

  • 小米手机如何将相册设置为私密相册(小米手机如何将锁屏开关移到桌面)

    小米手机如何将相册设置为私密相册(小米手机如何将锁屏开关移到桌面)

  • 苹果8长度是多少厘米(苹果 iphone 8长度)

    苹果8长度是多少厘米(苹果 iphone 8长度)

  • 苹果手机a1699是什么型号(苹果手机a1699是苹果几市场价多少钱)

    苹果手机a1699是什么型号(苹果手机a1699是苹果几市场价多少钱)

  • tt语音提现比例(tt语音提现要多少手续费)

    tt语音提现比例(tt语音提现要多少手续费)

  • 华为p40自拍杆怎么用(华为p40自拍杆怎么连接)

    华为p40自拍杆怎么用(华为p40自拍杆怎么连接)

  • b站会员购怎么退定金(b站会员购怎么看取件码)

    b站会员购怎么退定金(b站会员购怎么看取件码)

  • 合并单元格怎么复制粘贴(合并单元格怎么拆分)

    合并单元格怎么复制粘贴(合并单元格怎么拆分)

  • 天猫红包可以提现吗(天猫红包提交订单后会过期吗)

    天猫红包可以提现吗(天猫红包提交订单后会过期吗)

  • 小米8青春版可以插内存卡吗(小米8青春版可以开空调吗)

    小米8青春版可以插内存卡吗(小米8青春版可以开空调吗)

  • 有密码为什么连不上wifi(有密码为什么连不上wifi一直显示ip配置失败)

    有密码为什么连不上wifi(有密码为什么连不上wifi一直显示ip配置失败)

  • 电脑不支持5gwifi怎么办(电脑不支持5gwifi有什么办法)

    电脑不支持5gwifi怎么办(电脑不支持5gwifi有什么办法)

  • 钉钉直播点赞老师能看到是谁点的吗(钉钉直播点赞老师有钱吗)

    钉钉直播点赞老师能看到是谁点的吗(钉钉直播点赞老师有钱吗)

  • 表格字体怎么变大100(表格字体怎么变色)

    表格字体怎么变大100(表格字体怎么变色)

  • 苹果11音响怎么就一个响(苹果11音响怎么样)

    苹果11音响怎么就一个响(苹果11音响怎么样)

  • iphone7plus适合哪个系统(2021年用iphone7plus)

    iphone7plus适合哪个系统(2021年用iphone7plus)

  • qq音乐能剪辑音乐吗(qq音乐能剪辑音频文件吗)

    qq音乐能剪辑音乐吗(qq音乐能剪辑音频文件吗)

  • itunes我的设备在哪里(怎么在itunes上找到设备)

    itunes我的设备在哪里(怎么在itunes上找到设备)

  • 苹果x无面容怎么解锁(苹果x无面容怎么开面容)

    苹果x无面容怎么解锁(苹果x无面容怎么开面容)

  • 淘宝五皇冠可靠吗(淘宝五皇冠多少销量)

    淘宝五皇冠可靠吗(淘宝五皇冠多少销量)

  • 手淘首页流量怎么获取(手淘流量怎么来的)

    手淘首页流量怎么获取(手淘流量怎么来的)

  • win10重启(win10重启一直转圈)

    win10重启(win10重启一直转圈)

  • 在浏览器集成AI(chatgpt、new bing、bard )的必备扩展插件(浏览器集成什么意思)

    在浏览器集成AI(chatgpt、new bing、bard )的必备扩展插件(浏览器集成什么意思)

  • 印花税额计算及计税基础
  • 预扣预缴和汇算清缴
  • 应纳税所得额可以扣除哪些
  • 发票未到怎么暂估入账
  • 电子商业汇票怎么兑现
  • 税率3%的增值税专用发票
  • 在电子税务里怎么查以前年度亏损数据
  • 房地产会计预收账款明细科目
  • 供货方提供安装材料
  • 已认证未抵扣什么意思
  • 所得税多交但又不想去税务局退税怎样做账?
  • 地址变更工商局上门检查
  • 车辆购置税固定资产
  • 一般纳税人收取的下列款项中,应并入销售额
  • 冲红发票金额大怎么办
  • 网店提现要多久能到账
  • 如何查出账外收入
  • 表格怎样打印在一张a4纸上
  • bios术语
  • 被替换的账面价值题目
  • 如何在windows11上安装动态壁纸
  • 公司装修款账务处理
  • 广告公司的设计师多少钱一月
  • 付给他人押金的会计分录
  • 海康威视网页插件下载
  • php商品对比功能怎么用
  • php变量格式说法错误的是
  • 社保代扣代缴会计分录怎么做
  • 超像素和markpage的区别
  • pytorch with no grad
  • 勒索软件,网络不稳定
  • javaweb会话跟踪技术有哪些
  • 随手写-精美笔记本-日记本安卓下载
  • css怎么让文字垂直居中显示
  • 事业单位收到的罚款收入应纳入
  • 发现以前年度损益调整怎么记账
  • 买一赠一的销售方式
  • mysql中union什么意思
  • 小企业会计准则2023电子版
  • sqlserver2008r2怎么使用
  • access数据库如何
  • 物业公司广告费收入税率
  • 现金折扣是啥
  • 工会经费和残保金属于税费吗
  • 国外客户怎么付款给我们公司
  • 主营业务收入可以进一般户吗
  • 坏账准备计提的方法和比例
  • 房地产公司预收房款什么时候确认收入
  • 购货方尚未偿付的货款属于什么会计科目
  • 进项大于销项月末怎么处理
  • 公益性捐赠要确认递延吗
  • 发票开预付卡充值可以计入费用吗?
  • 公司开办期间的住宿费会计分录
  • 企业收到劳务费会计分录怎么做账
  • 被征用的不动产或者动产使用后应当怎样
  • 动态sql语句
  • mysql5.7.21安装
  • windows10怎样安装
  • 电脑网页字体设置
  • win7系统怎么设置不休眠
  • win7桌面没有了怎么办
  • win8.1系统升级
  • windows7库功能
  • win7系统笔记本怎么调节电脑亮度
  • win10一直重置
  • Cocos2d-x c++和java相互调用
  • php滚动代码
  • 批量创建用户
  • css分页样式
  • unity设置窗口位置
  • shell提示
  • js对象用法
  • Unity3d HDR和Bloom效果(高动态范围图像和泛光)
  • android对话框setview用法
  • python multinomial
  • js获取当前浏览器版本
  • 重庆市劳动监察大队官网
  • 浙江宁波江北区都有哪些大学?
  • 法人注册怎么注册
  • 税务局怎么知道房屋出租
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设