近似比对装置、近似比对方法、程序及记录介质

摘要

本发明的课题是，即使在输入字符串中包含错字和漏字、和设想的关键字有少许不同的表现，并且想提取的关键字数量多的情况下，也能够高速地提取。为了解决该课题，用跳跃词典制成部10对作为想提取的关键字而预先列入表中的关键字词典，制成包含由关键字自身、和从该关键字的全部字符位置至少删除1个字符后的字符串的集合组成的删除关键字的跳跃词典，并存储在跳跃词典存储部20中，通过用关键字提取部30进行输入字符串和上述跳跃词典的比对，从输入字符串中提取预先给予的关键字以及与该关键字近似的关键字，并和该关键词的出现位置一同进行输出。

主权项

一种近似比对装置，对用自然语言表述的输入字符串和预先给与的关键字进行比对，输出一致的关键字和该关键字的出现位置，该近似比对装置的特征在于具备：跳跃词典存储单元，针对预先给予的关键字，存储包含删除关键字的跳跃词典，该删除关键字由关键字自身、和从该关键字的全部字符位置至少删除1个字符后的字符串的集合组成；上述删除关键字由上述预先给予的关键字自身、和从该关键字的全部的字符位置pk起删除了连续的wk字后的字符串的集合组成，其中，1≤wk≤N，N是关键字的删除最大字符数量，上述跳跃词典对于上述集合中的各删除关键字的每一个，包含该删除关键字的删除字符位置pk、删除字符数量wk以及作为该删除关键字的根源的关键字即原关键字的组，作为该删除关键字的值，上述近似比对装置还具备关键字提取单元，上述关键字提取单元具有跳跃输入/跳跃词典比对单元，该跳跃输入/跳跃词典比对单元对上述输入字符串和存储在上述跳跃词典存储单元中的跳跃词典进行比对，对于与跳跃词典一致的全部关键字候补，如果删除关键字的删除字符数量wk为0，则分类为表示“关键字在输入字符串中完全一致地出现”的一致类型EM，如果删除关键字的删除字符数量wk比0大，则分类为表示“在输入字符串中存在删除字符的状态下和关键字一致”的一致类型DEL，将分类的结果作为一致类型，将一致类型、输入字符串中的一致开始位置、结束位置、错误开始位置、错误字符数量、原关键字存储在存储单元中，上述跳跃输入/跳跃词典比对单元制成一边使输入字符串的绝对跳跃位置p一次增加一个一边以跳跃幅度wi字进行了跳跃的字符串即跳跃输入，比对各跳跃输入和上述跳跃词典，对于和跳跃词典一致的全部关键字候补，计算在关键字上的相对跳跃位置pi，如果删除关键字的删除字符数量wk是0，则分类成表示“在输入字符串中存在插入字符的状态下 和关键字一致”的一致类型INS，如果删除关键字的删除字符数量wk大于0、并且输入字符串的相对跳跃位置pi和删除关键字的删除字符位置pk相等、并且输入字符串的跳跃宽度wi和删除关键字的删除字符数量wk相等，则分类为表示“在输入字符串中存在置换字符的状态下和关键字一致”的一致类型REP，将分类的结果作为一致类型，将一致类型、输入字符串中的一致开始位置、结束位置、错误开始位置、错误字符数量以及原关键字存储在存储单元中，其中，1≤wi≤M，M是输入字符串的最大跳跃幅度，其中，N＝M。