学习NLP的第6天——首字散列其余二分的字典树

主要通过《自然语言处理入门》(何晗)的第2章来学习散列函数。这里主要记录我在学习过程中整理的知识、调试的代码和心得理解&＃xff0c;以供其他学习的朋友参考。

在当前字典树的查询过程中&＃xff0c;需要不断在字典树中查询字符对应的节点。然而&＃xff0c;节点在结构中在相对位置是随机的&＃xff0c;因此&＃xff0c;在结构中查找节点时需进行一系列的比较&＃xff0c;而查询的效率则依赖于查询过程中所进行的比较的次数&＃xff0c;当字典树分支较多时&＃xff0c;查询速度会受到影响。

理想的情况是能够直接根据字符找到对应的节点&＃xff0c;因此必须在节点的存储位置和它所对应的字符之间建立一个确定的对应关系f&＃xff0c;使每个字符和结构中一个唯一的存储位置相对应。

这里将引入散列函数&＃xff0c;它用来将对象转换为整数。

散列函数&＃xff1a;也称哈希函数&＃xff08;Hash Function&＃xff09;&＃xff0c;哈希表中元素是由哈希函数确定的&＃xff0c;将数据元素的关键字K作为自变量&＃xff0c;通过一定的函数关系&＃xff08;称为哈希函数&＃xff09;&＃xff0c;计算出的值&＃xff0c;即为该元素的存储位置。

在我们之前的学习中&＃xff08;第3天——字典树&＃xff09;&＃xff0c;使用Python内置的dict作为散列表。但是由于Python没有char类型&＃xff0c;字符被视作长度为1的字符串&＃xff0c;所以实际调用的就是str的散列函数。由此导致在字符集中相邻的字符在散列值中相差很多&＃xff0c;不适合用来设计数据结构。

然而Java中的字符散列函数则将每个字符都映射为16位不重复的连续整数&＃xff0c;恰好是完美散列&＃xff0c;因此HanLP使用Java的字符散列函数来索引子节点。

但是&＃xff0c;也不可能所有节点都使用散列函数&＃xff0c;内存会随着字典树层数不断提高&＃xff0c;呈指数级膨胀。

故此&＃xff0c;采用只在根节点实施散列策略。此时的字典树如图所示。

学习使用教材&＃xff1a;《自然语言处理入门》(何晗)&＃xff1a;2.4.4

本文中为该教程的学习笔记和理解&＃xff0c;个人非常推荐这本书&＃xff0c;确实是非常好的教材。