trie树信息抽取之中文数字抽取

时间:2022-06-01 07:03:55

这一章讲一下利用trie树对中文数字抽取的算法。trie树是一个非常有用的数据结构,可以应用于大部分文本信息抽取/转换之中,后续会开一个系列,对我在实践中摸索出来的各种抽取算法讲开来。比如中文时间抽取,地址抽取等。

Trie树

trie树又称为前缀树,索引树,字典树。用来对字符串进行索引,每个节点存储一个字符,每个叶子节点代表一个字符串,即从根到它的路径上所有字符的序列。

这个结构有什么优点呢?可以快速的匹配一个目标字符串中存在的单词。换句话说,我有一个字典,是单词的集合,我把字典中所有的单词存储在trie树中,然后来一句话,我们可以利用trie树(字典树)快速的匹配出这句话中出现的字典中的所有单词,以及每个单词的位置。快速的意思是,复杂度近似于$O(L)$,其中$L$为这句话的长度,其速度不因字典的增大而降低。具体的匹配算法可以问百爷和姑爷,哦不,谷爷。

很多采用字典进行分词的分词器,都是用trie树进行分词的,比如IK分词。

利用trie树进行信息抽取,还有一个优点就是。逻辑非常清晰,非常方便扩展,大大降低了代码的复杂度和代码量,甚至后续扩展功能可以完全不用改动代码只需修改配置文件(字典)即可。

本章和后续章节中,我们用到的是扩展了的trie树,其叶子节点存储了相应数据,而且实现了无交叉的最大长度抽取器(分词器)以应对具体的业务。

中文数字抽取/转换

所谓中文数字的抽取/转换,就是下表:

原字符串 抽取/转换后
一千二百零8吨大米和三十袋盐 1208吨大米和30袋盐
第一二五分队 第125分队
二百1十五个苹果 215个苹果
。。。 。。。

 

名虽为中文数字抽取,其实对所有其它语言也完全适用,所做的只是修改配置文件即可。

下面介绍算法主要步骤:

1、trie树内容。

首先,我们要对汉字数字【零~十】这十一个字进行匹配,所以把这11个字插入trie树中,节点存储对应的数字;

然后,我们要对阿拉伯数字【0~9】这十个字进行匹配,所以把这10个字插入trie树,节点存储对应的数字;

 

以上是数字插入,共插入21个字。下面是带单位插入。

 

我们要对汉字的单位【十,百,千,万,亿,...】进行匹配,所以把这这5个单位的数字插入trie树中,对应节点值分别为【10,100,1000,10000,100000000,...】。

从1到9,组合上述的数字和这5个单位,共$(9+9)\times 5=120$个字:

插入词  节点存储
一千~九千 1000~9000
1千~9千  1000~9000
一万~九万 10000~90000
。。。 。。。

 

当然,若要对记账的大写字进行匹配,同样方法插入即可。

以上总共插入141个词以及附带数据,插入完毕。插入代码示例如下:

  String[] hanzi = new String[] { "零", "一", "二", "三", "四", "五", "六", "七",
				"八", "九", "十" };
		Map<String, Integer> unitMap = new HashMap<String, Integer>() {
			private static final long serialVersionUID = 1738199399754758349L;
			{
				put("十", 10);
				put("千", 1000);
				put("百", 100);
				put("万", 10000);
			}
		};
		for (Entry<String, Integer> entry : unitMap.entrySet()) {
			for (int i = 1; i < 10; i++) {
				Integer num = i * entry.getValue();
				numTrie.fillWithData(hanzi[i] + entry.getKey(), num);
				numTrie.fillWithData(i + entry.getKey(), num);
			}
		}
		for (int i = 0; i < hanzi.length; i++) {
			numTrie.fillWithData(hanzi[i], i);
		}    

上面代码只是示例,实际中可以把插入内容配置在文件中,启动时读取配置文件即可。以后扩展可以直接修改配置文件。

2、数字抽取/转换

第一步生成好了字典,打好了内功,这一步开始施展,拉出去遛一下,实现数字的抽取与转换。

现在以【一千二百零8吨大米】为例说明,首先利用上述字典匹配出的单词为:

单词 绑定数据 位置
一千 1000 0~2
二百 200 2~4
0 4~5
8 8 5~6

首先要区分数字边界,因为一句话中可能含有多个数字串。现在筛选来的都是兄弟,哦不,数字。这5个单词的位置首尾相连,可以融合成一个数字。

下面要做的就是,把绑定的数字全部加起来即可。$1000+200+0+8=1208$。OK,一个数字被我们抽取出来了,附带在原句子中的位置为0~6。

上面只是抽取出来的简单例子。实际中我们可能还要处理其它的格式,比如例子中的【第一二五分队】,我们所要出来的是【第125分队】,而按上述做法,出来的却是【第8分队】,非我所求。分析这类句子,我们发现这个数字字符串的每个元素都是个位(<10),若出现这种情况,我们不直接相加,而是直接显示其绑定数据的文本,然后拼接起来即可。

到此为止,已经把核心思想将清楚了。同志们会发现这个算法可扩展性非常强,稍微修改一下就可满足非常复杂的需求。下面附上相关的示例代码。

单词匹配:

  Segmenter<Integer> segmenter = new Segmenter<Integer>(numTrie);
		TranslateProcessor processor=new TranslateProcessor();
		segmenter.segment(str, processor);
		return processor.getResult();

 str为待抽取的句子,segmenter为分词器,抽取出来无交叉的最大长度单词,每抽取出来一个单词,调取TranslateProcessor进行处理,处理完毕后processor.getResult()可以获取转换后的结果。下面是TranslateProcessor的具体实现,算法的核心在这里:

	private static class TranslateProcessor implements LexemeProcessor<Integer> {
		String strResult = "";
		int numEndOffset = -1;
		int currentNum = 0;
		List<Integer> intResult=new ArrayList<Integer>();
		public String getResult() {
			return strResult;
		}

		@Override
		public void processLexeme(Lexeme<Integer> lex) {
			// 没有匹配到数字
			if (lex.getNodeData() == null) {
				// 若前面已经抽取出数字,数字加入结果,清空状态
				if (numEndOffset > -1) {
					strResult += currentNum;
					intResult.add(currentNum);
					numEndOffset = -1;
					currentNum = 0;
				}
				strResult += lex.getLexemeText();

				return;
			}
			// 数字匹配,并且紧邻,则进行合并,若上一个是个位数,不合并
			if (lex.getBeginPosition() == numEndOffset) {
				if (currentNum < 10) {
					strResult += currentNum;
					currentNum = 0;
				}
				currentNum += lex.getNodeData();
				numEndOffset = lex.getEndPosition();
				return;
			}
			currentNum = lex.getNodeData();
			numEndOffset = lex.getEndPosition();
		}
	}

 整个算法代码加起来不到100行。