汉字数字转阿拉伯数字

曹至梧 2019-11-11 12:24 更新
  1. 问题来源
  2. 要处理的问题
  3. 回溯的优化
  4. 编码

1. 问题来源

这个问题,是看到有人提到带中文数字的章节标题,要排序的问题引起的。比如对于:

title_list = [
'第一章',
'第三章',
'第五章',
'第四章',
'第二章',
]

想“正确”排序的话,你直接 title_list.sort() 是不行地:

zys@tower:~$ python3
Python 3.7.1 (default, Apr  1 2019, 01:01:48)
[GCC 7.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> title_list = [
... '第一章',
... '第三章',
... '第五章',
... '第四章',
... '第二章',
... ]
>>> title_list.sort()
>>> title_list
['第一章', '第三章', '第二章', '第五章', '第四章']
>>>

原因是在具体编码的码表中,“三”并不一定排在“二”前面,码表的编撰可不会特别考虑中文的排序这种事。

当然,对于不同的编码,这几个数字字符的相对位置,可能会有差异。上面的例子,只代表 Unicode 的一个结果。你转成 GB18030 或者 BIG5 的字节,结果可能不同。但这也足够说明,中文的数字依赖字典序是不可靠的。编码不同,结果就不同,这里的“字典序”本身就没有标准可言,如果你假设 Unicode ,那事实上这些字符的顺序也不是我们希望的“1 2 3 4”这样的顺序。

所以,这里就引出,我们可以把中文数字,转成阿拉伯数字,然后使用整数大小来排序就可以准确控制了。

光是 “一”,“二”,“三” 这些单个数字,倒是好办,我们写死一位数的映射都可以解决问题。接下来要说的,自然是更一般性的处理方法。

比如:

一千零一亿一千零一万一千零一

2. 要处理的问题

看上面的中文数字,直观地,可以看出中文数字其实是由“数字”和“单位”构成的:

这里我们先明确一下“十”这个“搅屎棍”的位置,它到底算数字,还是算单位。从我们日常习惯用法中看,它是两者都有的:

我们会把“十”作为单位处理,把它当数字时的情况作为特例。这样面对的特例,要比作为数字少得多。

如果我们能正确解析出汉字数字中的“数字”与“单位”的话,那么通过映射与简单运算,就可以得到需要的阿拉伯数字结果。

比如对于:

一千零一亿一千零一万一千零一

如果我们可以解析到:

那最后的结果就很容易了,是 1001 * 10^8 + 1001 * 10^4 + 1001

实际的问题当然没这么简单,上面的结果没问题,但首先你要能得到 1001 啊:

这才是我们从文字中看到的状况。

上面的结构,像是一颗树,按这个方向,为了方便定义节点和分支,我们可以整理得到:

继续分解:

对于这个结构,针对每一个节点,我们从下往上的顺序计算,就可以计算出每个节点的值——平行节点的值相加,父子节点的值相乘,过而得到最终值。再推广一下,整颗树从下往上顺序遍历就可以算出结果。

上面的分拆过程,有助于我们看到这个问题更深的一些信息,这些信息就是我们设计代码的参考。

我们的分拆,在思维上最开始可能是依据结果的倒推(我们知道“一千零一亿一千零一万一千零一”就是 1001 * 10^8 + 1001 * 10^4 + 1001),但我们写代码需要的是正向的逻辑,所以回到最初,去找出我们直觉上的逻辑依据:

对于:

一千零一亿一千零一万一千零一

我们怎么发现中间这些字应该提出来作为子节点?

一千零一亿一千零一一千零一

这个问题不难。

前面介绍了“数字”和“单位”的概念,我们把原始汉字中这两者分开:

零一亿零一零一

只看标色的“单位”,单位的值我们可以以 10 的指数来表示,从左右到绘制到直角坐标系上就是:

Gnuplot Produced by GNUPLOT 5.2 patchlevel 2 10 100 1000 10000 105 106 107 108 0 1 2 3 4 5 6 gnuplot_plot_1 gnuplot_plot_2 gnuplot_plot_3

从图上可以看出,我们要提出来的节点,正好是“波峰”。

再找个例子看看:

亿

Gnuplot Produced by GNUPLOT 5.2 patchlevel 2 10 100 1000 10000 105 106 107 108 0 2 4 6 8 10 12 gnuplot_plot_1 gnuplot_plot_2 gnuplot_plot_3

中文的习惯,报数是从大单位到小单位报,所以单位的连线应该是一直向下的。而突然向上,出现波峰,那么肯定是某个大单位的阶段性结束,前面说的那些都是为了“修辞”这个大单位的。

比如上图的,一,单位是变小的,但马上接了一个,至此,“万”这个范围,就结束了。

接着万,后面是 ,这是一个缩小的单位,没有特殊,再来就是亿,它是一个比“万”大的单位,同理,意味着“亿”这个范围结束了。

后面还有一个极点,在 上,也是同样的道理。

再往上看一层,整个过程,波峰处的单位顺序是 - 亿 -

这是否意味着子节点是这三个呢?

答案是否定的,“万亿”,是“万” x “亿”,不是“万” + “亿”。

所以正确的结构应该是:

- 亿 - 要得到这样的结构,又有什么规则?

回溯。

如果从左往右扫,即当碰到一个更大的单位时,需要回溯之前的节点,之前所有不比它大的单位,都应该成为其子节点。

到此,一般性的规则就介绍完了。(其实就这么点)

运用这个规则,就可以把中文数字,转成一个树结构,进而运算出阿拉伯数字结果。

3. 回溯的优化

这点算是经验之谈吧。

当一个场景,如果你从左到右遍历,需要回溯处理。那么换个方向,从右到左遍历,可能就不需要回溯了。如果遍历对象长度很大,这通常会带来可观的性能提升,及代码编写上的简单。

看之前示例的图和树结果:

Gnuplot Produced by GNUPLOT 5.2 patchlevel 2 10 100 1000 10000 105 106 107 108 0 2 4 6 8 10 12 gnuplot_plot_1 gnuplot_plot_2 gnuplot_plot_3

从左到右遍历之所以要回溯,是因为相对于这个树结构,从左到右遍历的过程是后找到父节点的。当你确定了一个父节点之后,它的子节点你需要重新组织调整。

如果我们把方向反过来,从右到左遍历的话,对于这个树,总是先遇到父节点。需要做的判断,仅仅是当前节点是否结束,然后开始一个新的父节点,并不需要不断折返来调整节点结构。

新节点开始的规则也简单明了,就是碰到了一个比之前都大的单位。

这些规则弄明白之后,编码就相对容易了。剩下的更多时间,是处理各种不合逻辑的例外情况,毕竟,人说话是依赖“习惯”,而不是“逻辑”。

4. 编码

4.1. 基本配置准备

就是数字和单位的映射,一些信息可以从网上搜索到:

num_map = {
    u'零': 0,
    u'〇': 0,
    u'两': 2,
    u'一': 1, u'二': 2, u'三': 3, u'四': 4, u'五': 5, u'六': 6, u'七': 7, u'八': 8, u'九': 9,
    u'壹': 1, u'贰': 2, u'叁': 3, u'肆': 4, u'伍': 5, u'陆': 6, u'柒': 7, u'捌': 8, u'玖': 9,
    u'廿': 20,
    u'卅': 30,
    u'卌': 40,
    u'圩': 50,
    u'圆': 60,
    u'进': 70,
    u'枯': 80,
    u'枠': 90,
}
rank_map = {
    u'十': 10, u'百': 100, u'千': 1000, u'万': 10000, u'亿': 100000000,
    u'拾': 10, u'佰': 100, u'仟': 1000,
    u'兆': 10 ** 16
}

后面如果找到新的词,也可以直接添加进去。

4.2. 解析中文

这一步做的事,是把原始中文字符转换成我们好处理的,中间状态的数据结构:

先用比较直接简单的例子来随时测试我们代码的基本功能,如: 四千五百万八千零一

简单地使用一个 dict ,有 typevalue 两个值就好。

设计上,一点技巧,一是把 0 单独处理,因为其实我们知道 有些特殊,但还没有事例来说明它到底特殊在哪里,所以,给它一点特殊待遇,专门设计一个 zero 的类型。

另一个,是在最后添加一个 complete 类型。这个明确的收尾信息,可以方便我们处理一些兜底工作,有助于更好的代码结构。(这个场景,类似于在一个迭代过程中,有一个临时容器。当迭代结束后,因为在迭代里面的代码并不知道迭代何时结束,所以一般你需要在迭代外再额外处理一下这个临时容器。如果在迭代过程中有一个明确的结束信号,比如明确知道这是最后一个条目了,那么在迭代内部就可以完成所有工作,代码会好看点。)

s = '四千五百万八千零一'

def parse(s):

    gen = []

    for c in s:
        if c in num_map:
            if num_map[c] == 0:
                gen.append({'type': 'zero'})
            else:
                gen.append({'type': 'number', 'value': num_map[c]})

        if c in rank_map:
            gen.append({'type': 'rank', 'value': rank_map[c]})

    gen.append({'type': 'complete'})
    return gen

执行 parse 可以得到这样的结果:

[
    {'type': 'number', 'value': 4},
    {'type': 'rank', 'value': 1000},
    {'type': 'number', 'value': 5},
    {'type': 'rank', 'value': 100},
    {'type': 'rank', 'value': 10000},
    {'type': 'number', 'value': 8},
    {'type': 'rank', 'value': 1000},
    {'type': 'zero'},
    {'type': 'number', 'value': 1},
    {'type': 'complete'}
]

对于理想状态,这个结果足够我们进行接下来的工作了。

4.3. 生成阿拉伯数字

这一步的一个正常过程,就是前面我们讲“规则”的过程。先做一个从左到右的正向遍历,不加回溯,处理一些最简单场景。接着加入更多场景,发现不加回溯搞不定。最后想到,换个方面遍历更直接方便。

项目上的代码并不是一蹴而就的,中间会经历很多次的重构。

这里就直接给出反向遍历的一个简单结果:

def generate(token_list):

    gen = token_list[:-1]
    gen.reverse()
    gen.append(token_list[-1])

    block = []
    level_rank = 1
    current_rank = 1
    for o in gen:

        if o['type'] == 'number':
            if not block:
                block.append([])
            block[-1].append(o['value'] * current_rank)

        if o['type'] == 'rank':
            rank = o['value']

            if not block:
                level_rank = rank
                current_rank = rank
                block.append([])
                continue

            if rank > level_rank:
                level_rank = rank
                current_rank = rank
                block[-1] = sum(block[-1])
                block.append([])
            else:
                current_rank = rank * level_rank
                block[-1] = sum(block[-1])
                block.append([])

        if o['type'] == 'zero':
            continue

        if (o['type'] == 'complete'):
            if isinstance(block[-1], list):
                block[-1] = sum(block[-1])

    return sum(block)

最终,这个 generate 就可以得到我们期望的结果, 45008001

不错的开始。

前面一直在提“理想状况”,是我们的代码只是针对 45008001 这一个普通例子完成。接下来,像这种业务场景,我们就可以做很多的测试用例,然后来“测试驱动完善”了。

4.4. 更多测试用例

下面的测试用例,绝大部分,是从: https://github.com/HaveTwoBrush/cn2an/blob/master/cn2an/cn2an_test.py 这里获取的。

TEST_SUIT = {
    u"一": 1,
    u"两": 2,
    u"十": 10,
    u"十一": 11,
    u"一十一": 11,
    u"一百一十一": 111,
    u"一千一百一十一": 1111,
    u"一万一千一百一十一": 11111,
    u"一十一万一千一百一十一": 111111,
    u"一百一十一万一千一百一十一": 1111111,
    u"一千一百一十一万一千一百一十一": 11111111,
    u"一亿一千一百一十一万一千一百一十一": 111111111,
    u"一十一亿一千一百一十一万一千一百一十一": 1111111111,
    u"一百一十一亿一千一百一十一万一千一百一十一": 11111111111,
    u"一千一百一十一亿一千一百一十一万一千一百一十一": 111111111111,
    u"壹": 1,
    u"拾": 10,
    u"拾壹": 11,
    u"壹拾壹": 11,
    u"壹佰壹拾壹": 111,
    u"壹仟壹佰壹拾壹": 1111,
    u"壹万壹仟壹佰壹拾壹": 11111,
    u"壹拾壹万壹仟壹佰壹拾壹": 111111,
    u"壹佰壹拾壹万壹仟壹佰壹拾壹": 1111111,
    u"壹仟壹佰壹拾壹万壹仟壹佰壹拾壹": 11111111,
    u"壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹": 111111111,
    u"壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹": 1111111111,
    u"壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹": 11111111111,
    u"壹仟壹佰壹拾壹亿壹仟壹佰壹拾壹万壹仟壹佰壹拾壹": 111111111111,
    u"一百零一": 101,
    u"一千零一": 1001,
    u"一千零一十一": 1011,
    u"一千一百零一": 1101,
    u"一万零一": 10001,
    u"一万零一十一": 10011,
    u"一万零一百一十一": 10111,
    u"一十万零一": 100001,
    u"一百万零一": 1000001,
    u"一千万零一": 10000001,
    u"一千零一万一千零一": 10011001,
    u"一千零一万零一": 10010001,
    u"一亿零一": 100000001,
    u"一十亿零一": 1000000001,
    u"一百亿零一": 10000000001,
    u"一千零一亿一千零一万一千零一": 100110011001,
    u"一千亿一千万一千零一": 100010001001,
    u"一千亿零一": 100000000001,

    u"十万": 100000,
    u"十万零一": 100001,
    u"十亿零一万零一": 1000010001,

    u"拾万零壹": 100001,
    u"拾亿零壹万零壹": 1000010001,

    u'一千一': 1100,
    u'一千一零一': 1101,
    u'一千零十亿': 101000000000,
    u'一一': 11,
    u'一二三': 123,
}

拿着这些测试用例去验证 parsegenerate 肯定会发现很多异常的,错误的情况。再针对这些错误的用例,去补充,修改代码就好。语言不是数学,追求系统层面的完备我觉得没必要,特殊情况一个 if 就行,实在不行,就再加一个 if

4.5. 完整实现

下面是一个我多次修改后的一个相对完整的实现,已经通过上面列出的所有测试。

# -*- coding: utf-8 -*-


num_map = {
    u'零': 0,
    u'〇': 0,
    u'两': 2,
    u'一': 1, u'二': 2, u'三': 3, u'四': 4, u'五': 5, u'六': 6, u'七': 7, u'八': 8, u'九': 9,
    u'壹': 1, u'贰': 2, u'叁': 3, u'肆': 4, u'伍': 5, u'陆': 6, u'柒': 7, u'捌': 8, u'玖': 9,
    u'廿': 20,
    u'卅': 30,
    u'卌': 40,
    u'圩': 50,
    u'圆': 60,
    u'进': 70,
    u'枯': 80,
    u'枠': 90,
}
rank_map = {
    u'十': 10, u'百': 100, u'千': 1000, u'万': 10000, u'亿': 100000000,
    u'拾': 10, u'佰': 100, u'仟': 1000,
    u'兆': 10 ** 16
}


s = u'一兆零一'


def convert(s):
    gen = []
    last_rank = 1

    #十 起头,其它 rank 起头, 都要补一,否则后面逻辑无法统一解释
    if s[0] in rank_map:
        gen.append({'type': 'number', 'value': 1})

    for c in s:
        if c in num_map:
            if num_map[c] == 0:
                #前面是数字,要补 rank , 1101
                if gen[-1]['type'] == 'number':
                    gen.append({'type': 'rank', 'value': int(last_rank / 10)})

                gen.append({'type': 'zero'})
            else:
                #连着两个数字, 如 一一
                if gen and (gen[-1]['type'] == 'number'):
                    gen.append({'type': 'rank', 'value': 10})
                gen.append({'type': 'number', 'value': num_map[c]})

        if c in rank_map:

            # 连续两个 rank ,合并
            # 十 有歧义,如果它前面带零不能合,如 一千零十亿, 还要把它改成数字
            # 不带零要合, 如 一十万零一
            last_rank = rank_map[c]
            if gen and gen[-1]['type'] == 'rank':
                if (len(gen) > 1) and (gen[-1]['value'] == 10) and (gen[-2]['type'] == 'zero'):
                    gen[-1]['type'] = 'number'
                    gen.append({'type': 'rank', 'value': rank_map[c]})
                else:
                    gen[-1]['value'] *= rank_map[c]
                continue

            gen.append({'type': 'rank', 'value': rank_map[c]})

    #补末位的省略, 如 一千一
    if gen and len(gen) > 1:
        if (gen[-1]['type'] == 'number') and (gen[-2]['type'] == 'rank'):
            gen.append({'type': 'rank', 'value': int(gen[-2]['value'] / 10)})

    gen.reverse()
    gen.append({'type': 'complete'})

    block = []
    level_rank = 1
    current_rank = 1
    for o in gen:

        if o['type'] == 'number':
            if not block:
                block.append([])
            block[-1].append(o['value'] * current_rank)

        if o['type'] == 'rank':
            rank = o['value']

            if not block:
                level_rank = rank
                current_rank = rank
                block.append([])
                continue

            if rank > level_rank:
                level_rank = rank
                current_rank = rank
                block[-1] = sum(block[-1])
                block.append([])
            else:
                current_rank = rank * level_rank
                block[-1] = sum(block[-1])
                block.append([])

        if o['type'] == 'zero':
            continue

        if (o['type'] == 'complete'):
            if isinstance(block[-1], list):
                block[-1] = sum(block[-1])

    return sum(block)


if __name__ == '__main__':
    print(s, convert(s))


# from: https://github.com/HaveTwoBrush/cn2an/blob/master/cn2an/cn2an_test.py

TEST_SUIT = {
    u"一": 1,
    u"两": 2,

    ...

    u'一千一': 1100,
    u'一千一零一': 1101,
    u'一千零十亿': 101000000000,
    u'一一': 11,
    u'一二三': 123,
}

count = 0
error = 0
for c, v in TEST_SUIT.items():
    r = convert(c)
    count += 1
    if v != r:
        error += 1
        print('ERROR', c, v, r)

print('SUM: {} ERROR: {}'.format(count, error))
评论
粤ICP备18106170号-1