[IR] Tolerant Retrieval & Spelling Correction & Language Model

时间:2023-01-24 15:57:47

Dictionary不一定是个list,它可以是多种形式。

放弃Hash的原因:

[IR] Tolerant Retrieval & Spelling Correction & Language Model

通常,tree是比较适合的结构。


From: http://www.cnblogs.com/v-July-v/archive/2011/06/07/2075992.html

  • B--tree

B-树又叫平衡多路查找树。一棵m阶的B-树 (m叉树)的特性如下

    1. 树中每个结点最多含有m个孩子(m>=2);
    2. 除根结点和叶子结点外,其它每个结点至少有[ceil(m / 2)]个孩子(其中ceil(x)是一个取上限的函数);
    3. 若根结点不是叶子结点,则至少有2个孩子(特殊情况:没有孩子的根结点,即根结点为叶子结点,整棵树只有一个根节点);
    4. 所有叶子结点都出现在同一层,叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点,实际上这些结点不存在,指向这些结点的指针都为null);
    5. 每个非终端结点中包含有n个关键字信息: (n,P0,K1,P1,K2,P2,......,Kn,Pn)。其中:
             a)   Ki (i=1...n)为关键字,且关键字按顺序升序排序K(i-1)< Ki。 
             b)   Pi为指向子树根的接点,且指针P(i-1)指向子树种所有结点的关键字均小于Ki,但都大于K(i-1)。 
             c)   关键字的个数n必须满足: [ceil(m / 2)-1]<= n <= m-1。

针对上面第5点,再阐述下:B树中每一个结点能包含的关键字(如之前上面的D H和Q T X)数有一个上界和下界。这两个界可以用一个称作B树的最小度数(算法导论中文版上译作度数)t(t>=2)表示。

    • 每个非根的结点必须至少含有t-1个关键字。每个非根的内结点至少有t个子女。如果树是非空的,则根结点至少包含一个关键字;
    • 每个结点可包含之多2t-1个关键字。所以一个内结点至多可有2t个子女。如果一个结点恰好有2t-1个关键字,我们就说这个结点是满的(而稍后介绍的B*树作为B树的一种常用变形,B*树中要求每个内结点至少为2/3满,而不是像这里的B树所要求的至少半满);
    • 当关键字数t=2(t=2的意思是,tmin=2,t可以>=2)时的B树是最简单的有很多人会因此误认为B树就是二叉查找树,但二叉查找树就是二叉查找树,B树就是B树,B树的真正最准确的定义为:一棵含有t(t>=2)个关键字的平衡多路查找树。每个内结点可能因此而含有2个、3个或4个子女,亦即一棵2-3-4树,然而在实际中,通常采用大得多的t值。

B树中的每个结点根据实际情况可以包含大量的关键字信息和分支(当然是不能超过磁盘块的大小,根据磁盘驱动(disk drives)的不同,一般块的大小在1k~4k左右);这样树的深度降低了,这就意味着查找一个元素只要很少结点从外存磁盘中读入内存,很快访问到要查找的数据。

[IR] Tolerant Retrieval & Spelling Correction & Language Model

  • B+-tree

B+-tree:是应文件系统所需而产生的一种B-tree的变形树。

一棵m阶的B+树和m阶的B树的差异在于:

1.有n棵子树的结点中含有n个关键字; (而B 树是n棵子树有n+1个关键字)

2.所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B-树的叶子节点并没有包括全部需要查找的信息)

3.所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键字。 (而B 树的非终节点也包含需要查找的有效信息)

[IR] Tolerant Retrieval & Spelling Correction & Language Model

为什么说B+-tree比B-树更适合实际应用中操作系统的文件索引和数据库索引?

1) B+-tree的磁盘读写代价更低

B+-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

举个例子,假设磁盘中的一个盘块容纳16bytes,而一个关键字2bytes,一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候,B 树就比B树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

2) B+-tree的查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。


WILD-CARD QUERIES

(1) prefix:B-tree搞定

  mon*

(2) suffix:反一下数据重新构树。B+tree

  *ing

(3) mon*ing:mon* 与 *ing 的results结合:

  mon* & *abc

(4) “Permuterm vocabulary 轮排索引”

首先Query → 标准形式:

P   →  Exact match P$
P* → $P*
*p → P$*
*p* → p*
p*q → q$p* p*q*r → ?
  先求r$p*,
  再filter out没有q的。
  找对应的posting list。
  返回Document Id。

(5) Bigram (扩展: K-gram indexes).
  i.e. castle for 3-gram 例如:$ca, cas, ast, tle, le$
  Bigram:
  Query: mon* can now be run as:
    $m AND mo AND on
  However, "moooomon" 这个是没有意义的,就filter out。


Spelling Correction

Spelling Tasks:
    A: Non-word Errors
    B: Real-word Errors
        * Typographical相似
        * Cognitive Errors相似

(1) Error detection
        A: 不在字典中
        B: 语法检测?

(2) Error correction
        A: Shortest weighted edit distance --> How to define?
            High noisy channel probability

B: Similar pronunciation/spelling
            Noisy channel, classifier

Define as following:

[IR] Tolerant Retrieval & Spelling Correction & Language Model

w单词拼写成xi的概率。得到 <Noisy channel probability for acress>

[IR] Tolerant Retrieval & Spelling Correction & Language Model

P(x|word) from Big Data.

P(x|word) from <Confusion matrix for spelling errors> like this:

[IR] Tolerant Retrieval & Spelling Correction & Language Model

Solving real-world spelling errors

Generate candidate set
• the word itself
• all single-letter edits that are English words
• words that are homophones
• 假设一个句子只有一个错误

Choose best candidates
• Noisy channel model
• Task-specific classifier


Language Model

Where to get the probabilities.
• Language model
• Unigram
• Bigram
• Etc
Channel model
• Same as for non-word spelling correction
• Plus need probability for no error, P(w|w)

查询似然模型:
P(d|q)=P(q|d) * P(d)/P(q)

P(d)默认为uniform distribution

P(q)是一个constant value

So, P(q|d)决定P(d|q)

[IR] Tolerant Retrieval & Spelling Correction & Language Model

对于Zero probability问题,采取策略:

[IR] Tolerant Retrieval & Spelling Correction & Language Model

在此基础上演变为混合模型:Jelinek-Mercer method

P(w|d) = λ*Pmle (w|Md ) + ( – λ)*Pmle (w|Mc )

[IR] Tolerant Retrieval & Spelling Correction & Language Model

-- Relationship to idf --

[IR] Tolerant Retrieval & Spelling Correction & Language Model


(1)

TERM

Doc1

Doc2

P(t) for Doc1

P(t) for Doc2

i

1

2

(1/22+3/38)/2=0.0622

(2/16+3/38)/2=0.1020

don't

1

1

(1/22+2/38)/2=0.0490

(1/16+2/38)/2=0.0576

want

1

(1/22+1/38)/2=0.0359

(0/16+1/38)/2=0.0132

to

1

(1/22+1/38)/2=0.0359

(0/16+1/38)/2=0.0132

go

1

(1/22+1/38)/2=0.0359

(0/16+1/38)/2=0.0132

a

1

(1/22+1/38)/2=0.0359

(0/16+1/38)/2=0.0132

groovy

1

(1/22+1/38)/2=0.0359

(0/16+1/38)/2=0.0132

king

1

(1/22+1/38)/2=0.0359

(0/16+1/38)/2=0.0132

of

1

1

(1/22+2/38)/2=0.0490

(1/16+2/38)/2=0.0576

love

3

3

(3/22+6/38)/2=0.1471

(3/16+6/38)/2=0.1727

you

2

(2/22+2/38)/2=0.0718

(0/16+2/38)/2=0.0263

can't

1

(1/22+1/38)/2=0.0359

(0/16+1/38)/2=0.0132

hurry

1

(1/22+1/38)/2=0.0359

(0/16+1/38)/2=0.0132

this

1

(1/22+1/38)/2=0.0359

(0/16+1/38)/2=0.0132

must

1

(1/22+1/38)/2=0.0359

(0/16+1/38)/2=0.0132

be

1

(1/22+1/38)/2=0.0359

(0/16+1/38)/2=0.0132

take

1

(1/22+1/38)/2=0.0359

(0/16+1/38)/2=0.0132

me

1

1

(1/22+2/38)/2=0.0490

(1/16+2/38)/2=0.0576

with

1

(1/22+1/38)/2=0.0359

(0/16+1/38)/2=0.0132

all

2

(0/22+2/38)/2=0.0263

(2/16+2/38)/2=0.0888

out

1

(0/22+1/38)/2=0.0132

(1/16+1/38)/2=0.0444

here

1

(0/22+1/38)/2=0.0132

(1/16+1/38)/2=0.0444

am

1

(0/22+1/38)/2=0.0132

(1/16+1/38)/2=0.0444

remember

1

(0/22+1/38)/2=0.0132

(1/16+1/38)/2=0.0444

is

1

(0/22+1/38)/2=0.0132

(1/16+1/38)/2=0.0444

tell

1

(0/22+1/38)/2=0.0132

(1/16+1/38)/2=0.0444

Total

22

16

(2)

Q1:
i remember you

M1: 0.0622*0.0132*0.0718
= 0.000058951

M2: 0.1020*0.0444*0.0263
= 0.000119107  !

Q2:
don't want you to love me

M1: 0.0490*0.0359*0.0718*0.0359*0.1471*0.0490
= 0.000000033  !

M2: 0.0576*0.0132*0.0263*0.0132*0.1727*0.0576
= 0.000000003

Q1:
Doc2 will be ranked first.

Q2:
Doc1 will be ranked first.

(3)

When
p(D1) = 0.7, p(D2) = 0.3,

p(Doc1|Q1)
= 0.000058951 * 0.7 = 0.000041266  !

p(Doc2|Q1)
= 0.000119107 * 0.3 = 0.000035732

p(Doc1|Q2)
= 0.000000033 * 0.7 = 0.000000023  !

p(Doc2|Q2)
= 0.000000003 * 0.3 = 0.000000001

Q1:
Doc1 will be ranked first. (change)

Q2:
Doc1 will be ranked first.

[IR] Tolerant Retrieval & Spelling Correction & Language Model的更多相关文章

  1. language model —— basic model 语言模型之基础模型

    一.发展 起源:统计语言模型起源于 Ponte 和 Croft 在 1998年的 SIGIR上发表的论文 应用:语言模型的应用很多: corsslingual retrieval distribute ...

  2. Traditional Language Model

    Traditional Language Model通常用于回答下述问题: How likely is a string of English words good English ? \(p_{LM ...

  3. 用CNTK搞深度学习 (二) 训练基于RNN的自然语言模型 &lpar; language model &rpar;

    前一篇文章  用 CNTK 搞深度学习 (一) 入门    介绍了用CNTK构建简单前向神经网络的例子.现在假设读者已经懂得了使用CNTK的基本方法.现在我们做一个稍微复杂一点,也是自然语言挖掘中很火 ...

  4. A Neural Probabilistic Language Model

    A Neural Probabilistic Language Model,这篇论文是Begio等人在2003年发表的,可以说是词表示的鼻祖.在这里给出简要的译文 A Neural Probabili ...

  5. tensorflow world language model

    上文提到了pytorch里的world language model,那么怎么能不说tensorflow的实现呢,还是以tensorflow ptb的代码为例说说. 地址: https://githu ...

  6. 论文分享&vert;《Universal Language Model Fine-tuning for Text Classificatio》

    https://www.sohu.com/a/233269391_395209 本周我们要分享的论文是<Universal Language Model Fine-tuning for Text ...

  7. language model ——tensorflow 之RNN

    代码结构 tf的代码看多了之后就知道其实官方代码的这个结构并不好: graph的构建和训练部分放在了一个文件中,至少也应该分开成model.py和train.py两个文件,model.py中只有一个P ...

  8. NLP问题特征表达基础 - 语言模型(Language Model)发展演化历程讨论

    1. NLP问题简介 0x1:NLP问题都包括哪些内涵 人们对真实世界的感知被成为感知世界,而人们用语言表达出自己的感知视为文本数据.那么反过来,NLP,或者更精确地表达为文本挖掘,则是从文本数据出发 ...

  9. SharePoint Search之&lpar;五&rpar;Query spelling correction— 查询拼写纠正

     Query spelling correction 在使用搜索引擎的时候.假设一不小心输入错误,或者对于某个词语记得不太清楚,搜索引擎会自己主动纠正: 这个功能可以缩短用户的时间,很好用.在Sh ...

随机推荐

  1. PHP开发调试环境配置(基于wampserver&plus;Eclipse for PHP Developers )

    1 软件准 WampServer 下载地址:http://www.wampserver.com/en/#download-wrapper    我下的是 里面包含了搭建PHP必须的4个软件:   1. ...

  2. magento -- 如何为商品分类(category)添加自定义属性

    在magento 中,由于使用了强大的EAV设计方法,我们可以很方便的给商品添加任意数量的属性.然而magento 没有给我们提供给商品分类添 加属性的功能.尽管我们知道magento所采用的EAV设 ...

  3. Unit Testing a zend-mvc application

    Unit Testing a zend-mvc application A solid unit test suite is essential for ongoing development in ...

  4. &lbrack;Webpack 2&rsqb; Tree shaking with Webpack 2

    The less code you can send to the browser, the better. The concept of tree shaking basically says th ...

  5. lesson1&colon;threadlocal的使用demo及源码分析

    本文中所使用的demo源码地址:https://github.com/mantuliu/javaAdvance 其中的类Lesson1ThreadLocal 本文为java晋级系列的第一讲,后续会陆续 ...

  6. 快排 quicksort 快速排序

    首先看这个 http://www.cnblogs.com/morewindows/archive/2011/08/13/2137415.html 看完后就没有什么不理解的了... PS 注意 凡是在一 ...

  7. mutilple output reduce cannot write

    package org.lukey.hadoop.classifyBayes; import java.io.BufferedReader; import java.io.IOException; i ...

  8. redis5&period;0新特性

    1. redis5.0新特性 1.1. 新的Stream类型 1.1.1. 什么是Stream数据类型 抽象数据日志 数据流 1.2. 新的Redis模块API:Timers and Cluster ...

  9. openssl - 数字证书的编程解析

    原文链接: http://www.cangfengzhe.com/wangluoanquan/37.html 这篇文章主要介绍PKI公钥体系中非常核心元素——数字证书的编程解析.在SSL,SET等安全 ...

  10. 初试PyOpenGL二 &lpar;Python&plus;OpenGL&rpar;基本地形生成与高度检测

    在上文中,讲述了PyOpenGL的基本配置,以及网格,球形的生成,以及基本的漫游.现在利用上一篇的内容,来利用高程图实现一个基本的地形,并且,利用上文中的第三人称漫游,以小球为视角,来在地形上前后左右 ...