文档章节

搜索引擎之词典查找

潘少online
 潘少online
发布于 2015/05/13 23:02
字数 2013
阅读 35
收藏 1

散列与最长词匹配:

  • 散列是一种常见的高效查找方法,它根据数组下标查询,所以速度快。首先根据词表构造散列表,具体来说就是用给定的散列函数构造词典到数组下标的映射,如果存在冲突,则根据选择的冲突处理方法解决地址冲突。然后可以在散列表的基础上执行散列查找。 

  • 不存在冲突的散列表叫做完美散列(perfect hash)。

  • 整词散列不适合分词的最长匹配查找方式。

  • 采用了逐字散列的方法,可以看成是一种逐字的完美散列


标准Trie树:

把单词中的每个字符逐字散列,整个词典组织成一个标准Trie树:

  • 除了根节点外的每个节点用一个字符标记,叫做splitChar

  • 类似有限状态机特别标记可以结束的状态,特别标记可以结束的节点

例子:一个词典的标准Trie树

S = { bear, bell, bid, bull, buy, sell, stock, stop }

使用数字搜索Trie树切分电话号码:

  • 问题:输入电话号码,返回区位编号

    例如输入:037163949884  返回:河南:郑州

  • 电话区位号码文件

0701:江西:鹰潭

0998:新疆:泽普县

0851:贵州:贵阳

0999:新疆:伊犁哈萨克自治州

0852:贵州:遵义


数字搜索Trie树:

类似按字做散列

区号有多长就有多少个节点对应

每个节点对应一个TrieNode

每个TrieNode 包含一个分隔字符splitChar 

例如:0 3 7 1 这个区号有四个节点对应

也就是说四个TrieNode对象

第一个对象中的splitChar属性是0

第二个对象中的splitChar属性是3

第三个对象中的splitChar属性是7



Trie树的特点:

  • 多路树

  • 三叉Trie树是三路

  • 数字搜索Trie树是10路

  • 压缩

  • 同样的前缀字符共享同样的存储单元,例如:北京、北京市两个词。北和京两个字的存储单元相同。

  • 使用逆Trie树来让后缀字符共享同样的存储单元,例如:复印机、打印机、传真机。共享“机”、“印”的存储单元。

  • 适合存储

  • 静态的数据

  • 词典不经常变化


实现数字搜索树-Trie节点:

public static final class TrieNode {
  protected TrieNode[] children; //孩子节点
  
  protected char splitChar; //分隔字符
  
  protected String area; //存储区位信息,类似HashMap中的Value
  
  /**
   * 构造方法
   *
   * @param splitchar 分隔字符
   */
  protected TrieNode(char splitchar) {
      children = new TrieNode[10];
      area = null;
      this.splitChar = splitchar;
  }
}

实现数字搜索树-生成树:

private TrieNode root;//树的根节点

//把词加入词典
private void addWord(String word, TrieNode root, String area) throws Exception {
    TrieNode currentNode = root;
    for (int i = 1; i < word.length(); i++) {
        char c0 = word.charAt(i);
        int ind = Integer.parseInt(word.substring(i, i + 1));
        if (null == currentNode.children[ind]) {
        	currentNode.children[ind] = new TrieNode(c0);
        }
        currentNode = currentNode.children[ind];
    }
    currentNode.area = area;
}

加载词典:

//从文本文件加载词库
public void load(String dicPath) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(dicPath), "gbk"));
    String data;
    while ((data = br.readLine()) != null) {
        String[] strs = data.trim().split(":");
        String area = strs[1] + ":" + strs[2];
        addWord(strs[0], root, area);
    }
    br.close();
}

词典路径:

//取得词典文件路径
public static String getDir(){
  String dir = System.getProperty("dic.dir");
  if (dir == null)
  dir = "/dic/";
  else if( !dir.endsWith("/"))
  dir += "/";
  return dir;
}
//调用过程
String dic = "/words.txt";
InputStream file = null;
if (System.getProperty("dic.dir") == null)
  file = getClass().getResourceAsStream(getDir()+dic);
else
  file = new FileInputStream(new File(getDir()+dic));
BufferedReader in = new BufferedReader(new InputStreamReader(file,"GBK"));

查找电话号码的过程:

//同时遍历输入串和树
public String search(String tel) throws Exception {
    TrieNode currentNode = root;
    for (int i = 1; i < tel.length(); i++) {//从树的根节点逐字查找
        currentNode = currentNode.children[(tel.charAt(i)-'0')];
        if (null != currentNode.area) {
            return currentNode.area;
        }
    }
    return null;//没找到
}

三叉Trie树:

    为了节省内存,三叉搜索树只有三个指针,一个指向左边的树,一个指向右边的树,还有一个向下,指向单词的下一个数据单元。三叉搜索树是二叉搜索树和数字搜索树的混合体。它有和数字搜索树差不多的速度但是和二叉搜索树一样只需要相对较少的内存空间。或者把三叉搜索树看成只有一个槽位的散列,通过左孩子和右孩子来解决冲突。

三叉Trie树的节点-TSTNode 

public final class TSTNode {
  /**  节点的值  */
  public Data data=null;// data属性可以存储词原文和词性、词频等相关的信息
  
  protected TSTNode loNode; //左边节点
  protected TSTNode eqNode; //中间节点
  protected TSTNode hiNode; //右边节点
  
  protected char splitchar; // 本节点表示的字符
  /**
   *  构造方法
   *
   *@param  splitchar  该节点表示的字符
   */
  protected TSTNode(char splitchar) {
  this.splitchar = splitchar;
  }
  
  public String toString()
  {
  return "splitchar:"+ splitchar;
  }
}

构建三叉Trie树

private TSTNode root;//树的根节点
private addWord(String key) //向词典树中加入一个单词的过程
{
  TSTNode currentNode = root; //从树的根节点开始查找
  int charIndex = 0; //查询词要比较的字符位置,从词的开头匹配
  while (true) {
  int charComp =key.charAt(charIndex) - currentNode.splitchar;//比较词的当前字符与节点的当前字符
  if (charComp == 0) {//相等
  charIndex++;
  if (charIndex == key.length()) {
  return currentNode;
  }
  if (currentNode.eqNode == null) {
  currentNode.eqNode = new TSTNode(key.charAt(charIndex));
  }
  currentNode = currentNode.eqNode;
  } else if (charComp < 0) {//小于
  if (currentNode.loNode == null) {
  currentNode.loNode = new TSTNode(key.charAt(charIndex));
  }
  currentNode = currentNode.loNode;
  } else {//大于
  if (currentNode.hiNode == null) {
  currentNode.hiNode = new TSTNode(key.charAt(charIndex));
  }
  currentNode = currentNode.hiNode;
  }
  }
}

查找三叉Trie树

protected TSTNode getNode(String key, TSTNode startNode) {//从startNode开始,查找key
  TSTNode currentNode = startNode; //匹配过程中的当前节点的位置
  int charIndex = 0;//查询词要比较的字符位置
  char cmpChar = key.charAt(charIndex);
  int charComp;
  while (true) {
  if (currentNode == null) {
  return null;//没找到
  }
  charComp = cmpChar - currentNode.splitchar;
  if (charComp == 0) {//相等
  charIndex++;
  if (charIndex == len) {//找到了
  return currentNode;
  }
  else{
  cmpChar = key.charAt(charIndex);
  }
  currentNode = currentNode.eqNode;
  } else if (charComp < 0) {//小于
  currentNode = currentNode.loNode;
  } else {//大于
  currentNode = currentNode.hiNode;
  }
  }
}

最大长度匹配

public String matchLong(String key,int offset) {//输入字符串和匹配的开始位置
  String ret = null; //存储候选最长匹配词
  TSTNode currentNode = rootNode;
  int charIndex = offset;
  while (true) {
  if (currentNode == null) {
  return ret;
  }
  int charComp = key.charAt(charIndex) - currentNode.spliter;
  
  if (charComp == 0) {
  charIndex++;
  if(currentNode.data != null){
  ret = currentNode.data; //候选最长匹配词
  }
  if (charIndex == key.length()) {
  return ret; //已经匹配完
  }
  currentNode = currentNode.eqNode;
  } else if (charComp < 0) {
  currentNode = currentNode.loNode;
  } else {
  currentNode = currentNode.hiNode;
  }
  }
}

测试最大长度匹配

String sentence = "大学生活动中心";//输入字符串
int offset = 0;//匹配的开始位置
String ret = dic.matchLong(sentence,offset);
System.out.println(sentence+" match:"+ret);

HashMap vs Trie树

  • HashMap和Trie树都支持

  • contains(key)

  • get(key)

  • Trie树还支持前缀查找


匹配英文

/**对连续英文字母组成的英文采用专门的方法来匹配
* @param start 开始位置
 * @param key  输入字符串
 * @param length 字符串长度
 * @return 返回第一个不是英文的位置
 */
public int matchEnglish (int start, char[] key, int length)
{
  int i = start;
  while(i<length)
  {
  char c = key[i];
  if( c>='a'&&c<='z' || c>='A'&&c<='Z' )
  {
  ++i;
  }
  else
  {
  break;
  }
  } 
  return i;
}

Trie树平衡

    树是否平衡取决于单词的读入顺序。如果按排序后的顺序插入,则生成方式最不平衡。单词的读入顺序对于创建平衡的三叉搜索树很重要。通过选择一个排序后的数据单元集合的中间值,并把它作为开始节点。

Trie树平衡顺序

取得平衡的单词排序类似于对扑克洗牌。

想象有若干张扑克牌,每张牌对应一个单词,先把牌排好序。然后取最中间的一张牌,单独放作一摞牌。剩下的牌就分成了两摞。左边一摞牌中也取最中间的一张放在取出来的那张牌后面。右边一摞牌中也取最中间的一张放在取出来的牌后面,依次类推。 


平衡顺序输出词典

//在调用此方法前,先把词典数组k排好序
void outputBalanced(BufferedWriter fp,ArrayList<String> k,int offset, int n)
{
    int m;
    if (n < 1) {
        return;
    }
    m = n >> 1; //m=n/2
    
    String item= k.get(m + offset);
    fp.write(item);//把词条写入到文件
    fp.write('\n');
  
    outputBalanced(fp,k,offset, m); //输出左半部分
    outputBalanced(fp,k, offset + m + 1, n - m - 1); //输出右半部分
}

三叉Trie树

  • 词典中包括如下的8个词语:

  • 大  大学   大学生   活动   生活   中   中心  心 

  • 为了形成平衡的Trie树,把词先排序,排序后为:

  • 中  中心  大  大学 大学生  心  活动  生活



© 著作权归作者所有

潘少online

潘少online

粉丝 19
博文 60
码字总数 122122
作品 3
深圳
程序员
私信 提问
.NET Core中文分词组件jieba.NET Core

特点 支持三种分词模式: 支持繁体分词 支持添加自定义词典和自定义词 jieba.NET Core 用法 下载代码使用VS 2017 打开,或者使用VS Code 打开项目。 选择jieba.NET 为起始项目,Program.cs ...

jjjyyy66
2017/05/15
0
0
海量数据搜索---demo展示百度、谷歌搜索引擎的实现

在我们平常的生活工作中,百度、谷歌这些搜索网站已经成为了我们受教解惑的学校,俗话说得好,“有问题找度娘”。那么百度是如何在海量数据中找到自己需要的数据呢?为什么它搜索的速度如此之...

宜信技术学院
09/05
2.5K
0
【iOS】正则表达式抓取网页数据制作小词典

应用程序不一定要自己去提供数据,有现成的数据学会去用才好。 网络很大,各种搜索引擎每天到处爬。本文通过正则表达式抓取网站的数据来做一个小词典。 一、正则表达式的使用 1. 确定匹配方案...

xn4545945
2014/07/11
0
0
Python中文分词组件 - jieba

jieba "结巴"中文分词:做最好的Python中文分词组件 "Jieba" Feature 支持三种分词模式: 精确模式,试图将句子最精确地切开,适合文本分析; 全模式,把句子中所有的可以成词的词语都扫描出...

fxsjy
2012/10/03
149K
9
结巴分词 0.34 发布,Python 中文分词组件

结巴分词 0.34 发布,更新内容如下: 2014-10-20: version 0.34 1. 提升性能,词典结构由Trie改为Prefix Set,内存占用减少2/3, 详见:https://github.com/fxsjy/jieba/pull/187;by @gumbl...

fxsjy
2014/10/20
2.9K
8

没有更多内容

加载失败,请刷新页面

加载更多

使用zabbix自带的模板监控MySQL自带

一、安装zabbix server 略 二、安装zabbix agent 略 三、给主机套自带的模板 略 四、创建授权用户 mysql> grant all on *.* to 'zabbix'@'localhost' identified by 'musingtec2019';Quer......

雁南飞丶
19分钟前
6
0
notepad++快捷键

notepad++也情有独钟,最近发现了一个快捷键,就是选中单词,ctrl+shift+enter。不过现在想知道一个快捷键,假设有三行代码,选中后一般按TAB就可以三行全部缩进. Notepad++绝对是windows下进...

zhengzhixiang
40分钟前
6
0
区块链背景是什么?区块链的意义是什么?

一、前言 区块链技术的首次也是最著名的应用是比特币,一个在2009年1月初正式上线运行的去中心化数字货币应用,他的创始人叫中本聪,但目前大家并不知道此人的真实身份。 比特币不同于现代国...

daxiongdi
46分钟前
5
0
在Bash中循环浏览文件内容

如何使用Bash遍历文本文件的每一行? 使用此脚本: echo "Start!"for p in (peptides.txt)do echo "${p}"done 我在屏幕上得到以下输出: Start!./runPep.sh: line 3: syntax error......

技术盛宴
48分钟前
8
0
史上最强IP正则表达式

port ([0-9]|[1-9]\\d{1,3}|[1-5]\\d{4}|6[0-4]\\d{4}|65[0-4]\\d{2}|655[0-2]\\d|6553[0-5]) ipv4 ^((25[0-5]|2[0-4]\\d|[01]?\\d\\d?)\\.){3}(25[0-5]|2[0-4]\\d|[01]?\\d\\d?)$ ipv4+mask......

蜗牛伊
51分钟前
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部