拼写检查编程题详解-BK树算法

2018/11/12 00:09
阅读数 299

目录

问题:1035:拼写检查

分析:

编辑距离:

BK树:

构造BK树:

查询相似词:

推论:

C++AC代码:


问题:1035:拼写检查

查看    提交   统计     提示        提问

总时间限制:2000ms           内存限制:65536kB

描述

现在有一些英语单词需要做拼写检查,你的工具是一本词典。需要检查的单词,有的是词典中的单词,有的与词典中的单词相似,你的任务是发现这两种情况。单词A与单词B相似的情况有三种:

1、删除单词A的一个字母后得到单词B;

2、用任意一个字母替换单词A的一个字母后得到单词B;

3、在单词A的任意位置增加一个字母后得到单词B。

你的任务是发现词典中与给定单词相同或相似的单词。

 

输入

第一部分是词典中的单词,从第一行开始每行一个单词,以"#"结束。词典中的单词保证不重复,最多有10000个。
第二部分是需要查询的单词,每行一个,以"#"结束。最多有50个需要查询的单词。
词典中的单词和需要查询的单词均由小写字母组成,最多包含15个字符。

输出

按照输入的顺序,为每个需要检查的单词输出一行。如果需要检查的单词出现在词典中,输出“?x is correct",?x代表需要检查的单词。如果需要检查的单词没有出现在词典中,则输出"?x: ?x1 ?x2 ...?xn",其中?x代表需要检查的单词,?x1...?xn代表词典中与需要检查的单词相似的单词,这些单词中间以空格隔开。如果没有相似的单词,输出"?x:"即可。

样例输入

i
is
has
have
be
my
more
contest
me
too
if
award
#
me
aware
m
contest
hav
oo
or
i
fi
mre
#

样例输出

me is correct
aware: award
m: i my me
contest is correct
hav: has have
oo: too
or:
i is correct
fi: i
mre: more me

查看         提交        统计   提示          提问

分析:

之前写了这道题普通的解法——分情况讨论,详见拼写检查编程练习题。如果我们想要获取和字典中单词有至多2个字母之差的单词,那么该如何处理,如果还是分情况讨论的话会非常复杂。这个问题难就难在,根据定义操作可以是单词任意位置上的,似乎不遍历字典是不可能完成的。那么该怎么解决呢?接下来慢慢进行分析。另外我们在使用搜索引擎时,有没有发现即使输错几个字母,搜索引擎依然能很快给我们推荐出想要的单词,非常智能。

编辑距离:

这里,我们只需通过修改一个字母即可将单词A转换为单词B。在更一般的情况下,任何两个单词都可以经过有限次的增加、删除、替换某个字母相互转换。这时我们就可以使用最少多少步的增加、删除、修改操作将两个单词(字符串)互相转换,来度量两个单词(字符串)有多像,换句话说就是两个字符串的相似度是多少。1965年,俄国科学家Vladimir Levenshtein给字符串相似度做出了一个明确的定义叫做Levenshtein距离,我们通常叫它“编辑距离”。字符串A到B的编辑距离是指,只用插入、删除和替换三种操作,最少需要多少步可以把A变成B。Levenshtein给出了编辑距离的一般求法,就是大家都非常熟悉的经典动态规划问题。求编辑距离问题请见编辑距离算法详解:Levenshtein Distance算法——动态规划问题。

BK树:

在自然语言处理中,这个概念非常重要,例如我们可以根据这个定义开发出一套半自动的校对系统:查找出一篇文章里所有不在字典里的单词,然后对于每个单词,列出字典里与它的Levenshtein距离小于某个数n的单词,让用户选择正确的那一个。n通常取到2或者3,或者更好地,取该单词长度的1/4等等。这个想法倒不错,但算法的效率成了新的难题:查字典好办,建一个Trie树即可;但怎样才能快速在字典里找出最相近的单词呢?这个问题难就难在,Levenshtein的定义可以是单词任意位置上的操作,似乎不遍历字典是不可能完成的。现在很多软件都有拼写检查的功能,提出更正建议的速度是很快的。它们到底是怎么做的呢?1973年,Burkhard和Keller提出的BK树有效地解决了这个问题。这个数据结构强就强在,它初步解决了一个看似不可能的问题,而其原理非常简单。

BK树或者称为Burkhard-Keller树,是一种基于树的数据结构,被设计于快速查找近似字符串匹配,比方说拼写纠错,或模糊查找,当搜索”aeek”时能返回”seek”和”peek”。BK树在1973年由Burkhard和Keller第一次提出,论文在这《Some approaches to best match file searching》。这是网上唯一的ACM存档,需要订阅。更细节的内容,可以阅读这篇论文《Fast Approximate String Matching in a Dictionary》。

首先,我们先观察Levenshtein距离的性质。令d(x,y)表示字符串x到y的Levenshtein距离,那么显然:

1. d(x,y) = 0 当且仅当 x=y         (Levenshtein距离为0 <==> 字符串相等)

2. d(x,y) = d(y,x)                        (从x变到y的最少步数就是从y变到x的最少步数)

3. d(x,y) + d(y,z) >= d(x,z)         (从x变到z所需的步数不会超过x先变成y再变成z的步数)   

最后这一个性质叫做三角形不等式(Triangle Inequality)。就好像一个三角形一样,两边之和必然大于第三边。给某个集合内的元素定义一个二元的“距离函数”,如果这个距离函数同时满足上面说的三个性质,我们就称它为“度量空间”。我们的三维空间就是一个典型的度量空间,它的距离函数就是点对的直线距离。度量空间还有很多,比如Manhattan距离,图论中的最短路,当然还有这里提到的Levenshtein距离。就好像并查集对所有等价关系都适用一样,BK树可以用于任何一个度量空间。

构造BK树:

建树的过程有些类似于Trie树。首先我们随便找一个单词作为根(比如game)。以后插入一个单词时首先计算单词与根的Levenshtein距离:如果这个距离值是该节点处第一次出现,建立一个新的儿子节点;否则沿着对应的边递归下去。例如,我们插入单词fame,它与game的距离为1,于是新建一个儿子,连一条标号为1的边;下一次插入gain,算得它与game的距离为2,于是放在编号为2的边下。再下次我们插入gate,它与game距离为1,于是沿着那条编号为1的边递归下去,递归地插入到fame所在子树;gate与fame的距离为2,于是把gate放在fame节点下,边的编号为2。

每个节点有任意个子节点,每条边有个值表示编辑距离。所有子节点到父节点的边上标注n表示编辑距离恰好为n。

查询相似词:

查询操作异常方便。如果我们需要返回与错误单词距离不超过n的单词,这个错误单词与树根所对应的单词距离为d,那么接下来我们只需要递归地考虑编号在d-n到d+n范围内的边所连接的子树。假如被检查的节点与搜索单词的距离d小于n,则返回该节点并继续查询。由于n通常很小,因此每次与某个节点进行比较时都可以排除很多子树。   

BK树是多路查找树,并且是不规则的(但通常是平衡的)。试验表明,一次查询所遍历的节点不会超过所有节点的5%到8%,两次查询则一般不会17-25%,效率远远超过暴力枚举。适当进行缓存,减小Levenshtein距离常数n可以使算法效率更高。需要注意的是,如果要进行精确查找,也可以非常有效地通过简单地将n设置为0进行。

举个例子,假如我们输入一个gaie,程序发现它不在字典中。现在,我们想返回字典中所有与gaie距离为1的单词。我们首先将gaie与树根game进行比较,得到的距离d=1。由于Levenshtein距离满足三角形不等式,因此现在所有离game距离超过2的单词全部可以排除了。比如,以aim为根的子树到game的距离都是3,而game和gaie之间的距离是1,那么aim及其子树到gaie的距离至少都是2。于是,现在程序只需要沿着标号范围在1-1到1+1里的边继续走下去。我们继续计算gaie和fame的距离,发现它为2,于是继续沿标号在1和3之间的边前进。遍历结束后回到game的第二个节点,发现gaie和gain距离为1,输出gain并继续沿编号为1或2的边递归下去(那条编号为4的边连接的子树又被排除掉了)……  

推论:

这里可能有人会有疑问为啥查找的时候只需要递归地考虑编号在d-n到d+n范围内的边就可以了?接下来让我们根据levenshtein距离的性质进行推导:

我们了解了编辑距离所表达的度量的空间之后,再来看下Burkhard和Keller所观察到的关键结论。

如果我们需要返回与错误单词gaie距离不超过n的单词,这个错误单词与树根game(可用任意字符串A代替)所对应的单词距离为d,因为levenshtein距离的性质(3)三角形不等式成立,则满足与gaie距离在n范围内的另一个字符串B,其与树根game的距离最大为d+n,最小为d-n。

推论如下:

d(gaie, B) + d(B, A) >= d(gaie, A),  即 d(gaie, B) + d(A,B) >= d    

                                                     -->  d(A,B) >= d - d(gaie, B) >= d - n

d(A, B) <= d(A,gaie) + d(gaie, B),   即 d(A, B) <= d + d(gaie, B) <= d + n

其实,还可以得到 d(gaie, A) + d(A,B) >= d(gaie, B)                   

                        --> d(A,B) >= d(gaie, B) - d(gaie, A) 

                        --> d(A,B) >= 1 - d >= 0 (gaie与B不等) 由于 A与B不是同一个字符串,所以d(A,B)>=1

所以, min{1, d - n} <= d(A,B) <= d + n,这是更为完整的结论。

C++AC代码:

#include <iostream>
#include <string>
#include <map>

using namespace std;
struct nodew{             //存储单词信息,因为POJ要求输出相似词时,需按照读入顺序输出,所以得设置单词的顺序
    int order;
    string word;
};

typedef struct treeNode{                    //结构体,存储树节点,我这里使用map容器,没有使用指针,性质差不多。但map会节省点空间。
    struct nodew word;
    map<int, struct treeNode*> bkTreeNode;  //map容器存储孩子节点,map的key对应编辑距离,value值对应结点。
}BKTreeNode;
bool isSame = false;                        //标识两个单词是否相同
map<int,string> result;                     //存储距离为1时的结果集

int levenSTDistance(string x, string y);                   //计算字符串x和字符串y的levenshtein距离
int minOfTreeNum(int a, int b, int c);                     //返回a,b,c三个数中最小值
void queryWord(BKTreeNode* tNode, string word);            //查询单词是否在字典,如果不在的话返回距离为1的结果集
void buildTree(BKTreeNode* tNode, struct nodew nodBuild);  //构造BK树
BKTreeNode* newTreeNode();                                 //初始化节点。

int main()
{
    string dic;                        //词典单词
    string word;                       //待查询单词
    //vector<string>::iterator vIter;  //一开始没有考虑顺序,所以换为了map
    map<int,string>::iterator mIter;   //map容器的迭代器
    string temp;   //中间变量
    int cnt = 1;   //为字典中单词编号,排顺序

    cin >> dic;
    BKTreeNode* root = newTreeNode();
    struct nodew nodetemp;     //单词结构体,初始化完成后再存入词典
    nodetemp.word = dic;
    nodetemp.order = 0;        //为树根单词编号为0
    root->word = nodetemp;
    while(1)
    {
        cin >> dic;
        if(dic == "#")
        {
            break;
        }
        nodetemp.order = cnt++;    //为单词标记读入顺序
        nodetemp.word = dic;       //初始化单词
        buildTree(root,nodetemp);  //构造BK树
    }
    while(1)
    {
        cin >>word;
        if(word == "#")
        {
            break;
        }
        isSame = false;        //每查完一个单词之后置为false
        result.clear();        //将结果集清空
        queryWord(root,word);  //在BK树中查找满足要求的单词
        if(!isSame)            //如果字典中没有找到,则输出相似单词
        {
            cout << word << ":";
            for(mIter = result.begin(); mIter != result.end(); mIter++) //迭代输出结果集
            {
                temp = mIter->second;
                cout << " " << temp;
            }
        }else{
            cout << word <<" is correct" ;    //在词典中找到的话,直接输出正确。
        }
        cout << endl;
    }
    return 0;
}


//初始化节点
BKTreeNode* newTreeNode()
{
    BKTreeNode * node = new BKTreeNode;
    return node;
}

void buildTree(BKTreeNode* tNode, struct nodew nodBuild) //构造BK树
{
    string newNode = nodBuild.word;                   //新进来的结点
    string dicNode = tNode->word.word;                //BK树中的节点
    int distance = levenSTDistance(newNode, dicNode); //计算编辑距离
    map<int,BKTreeNode*>::iterator iter;              //BK树子树迭代器

    iter = tNode->bkTreeNode.find(distance);          //查找孩子树种是否存在
    if(iter != tNode->bkTreeNode.end())               //存在的话迭代插入孙子结点
    {
        buildTree(iter->second, nodBuild);
    }else{                                            //不存在的话插入孩子结点
        BKTreeNode* tempNode = newTreeNode();
        tempNode->word = nodBuild;
        tNode->bkTreeNode[distance] = tempNode;
    }
}

void queryWord(BKTreeNode* tNode, string word)
{
    string dicNode = tNode->word.word;
    int ord;
    int distance = levenSTDistance(dicNode, word);
    int i;
    map<int, BKTreeNode*>::iterator iter;

    if(distance == 0)
    {
        isSame = true;
    }else{
        if(distance == 1){
                ord = tNode->word.order;
                result[ord] = dicNode;
        }
        i = max(1,distance-1);
        for(; i <= distance+1 ; i++)
        {
            iter = tNode->bkTreeNode.find(i);
            if(iter != tNode->bkTreeNode.end())
            {
                queryWord(iter->second, word);
            }

        }
    }
}

int minOfTreeNum(int a, int b, int c)  //返回a,b,c三个数中最小值
{
    int minNum = a;
    if(minNum > b )
    {
        minNum = b;
    }
    if(minNum > c )
    {
        minNum = c;
    }
    return minNum;
}

int levenSTDistance(string x, string y)  //计算字符串x和字符串y的levenshtein距离
{
    int lenx = x.length();
    int leny = y.length();
    int levenST[lenx+1][leny+1];  //申请一个二维数组存放编辑距离
    int eq = 0;                   //存放两个字母是否相等
    int i,j;

    //初始化二维数组,也就是将最简单情形的levenshtein距离写入
    for(i=0; i <= lenx; i++)
    {
        levenST[i][0] = i;
    }
    for(j=0; j <= leny; j++)
    {
        levenST[0][j] = j;
    }

    //将串x和串y中的字母两两进行比较,得出相应字串的编辑距离
    for(i=1; i <= lenx; i++ )
    {
        for(j=1; j <= leny; j++)
        {
            if(x[i-1] == y[j-1])
            {
                eq = 0;
            }else{
                eq = 1;
            }
            levenST[i][j] = minOfTreeNum(levenST[i-1][j] + 1, levenST[i][j-1] + 1, levenST[i-1][j-1] + eq);
        }
    }
    return levenST[lenx][leny];
}

注意:POJ上面要求数组必须是按照输入的顺序输出。

参考资料:http://www.matrix67.com/blog/?s=bk%E6%A0%91

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部