概述

我得到了一组可能的有效 block ，可用于拆分文本(如果可能)。

我如何使用这些 block 拆分给定的文本，以便根据结果 block 的数量优化(最小化)结果？

测试套件

if __name__ == "__main__":
    import random
    import sys

    random.seed(1)

    # 1) Testing robustness
    examples = []
    sys.stdout.write("Testing correctness...")
    N = 50
    large_number = "3141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481"
    for i in range(100):
        for j in range(i):
            choices = random.sample(range(i), j)
            examples.append((choices, large_number))

    for (choices, large_number) in examples:
        get_it_done(choices, large_number)
    sys.stdout.write("OK")

    # 2) Testing correctness
    examples = [
        # Example1 ->
        # Solution ['012345678910203040506070', '80', '90', '100', '200', '300', '400', '500', '600', '700', '800', '900']
        (
            [
                "0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
                "10", "20", "30", "40", "50", "60", "70", "80", "90",
                "100", "200", "300", "400", "500", "600", "700", "800", "900",
                "012345678910203040506070"
            ],
            "0123456789102030405060708090100200300400500600700800900"
        ),
        # Example2
        ## Solution ['100']
        (
            ["0", "1", "10", "100"],
            "100"
        ),
        # Example3
        ## Solution ['101234567891020304050', '6070809010020030040050', '0600700800900']
        (
            [
                "10", "20", "30", "40", "50", "60", "70", "80", "90",
                "012345678910203040506070",
                "101234567891020304050",
                "6070809010020030040050",
                "0600700800900"
            ],
            "10123456789102030405060708090100200300400500600700800900"
        ),
        # Example4
        ### Solution ['12', '34', '56', '78', '90']
        (
            [
                "12", "34", "56", "78", "90",
                "890",
            ],
            "1234567890"
        ),
        # Example5
        ## Solution ['12', '34']
        (
            [
                "1", "2", "3",
                "12", "23", "34"
            ],
            "1234"
        ),
        # Example6
        ## Solution ['100', '10']
        (
            ["0", "1", "10", "100"],
            "10010"
        )
    ]

    score = 0
    for (choices, large_number) in examples:
        res = get_it_done(choices, large_number)
        flag = "".join(res) == large_number
        print("{0}\n{1}\n{2} --> {3}".format(
            large_number, "".join(res), res, flag))
        print('-' * 80)
        score += flag

    print(
        "Score: {0}/{1} = {2:.2f}%".format(score, len(examples), score / len(examples) * 100))

    # 3) TODO: Testing optimization, it should provide (if possible)
    #          minimal cases

问题

我如何在不使用蛮力方法的情况下在 python 上解决这个问题？

最佳答案

使用动态规划，您可以构造一个列表(l0, l1, l2, ... ln-1)，其中n 是您的字符数输入字符串，li 是到达输入字符串的字符 i 所需的最少 block 数。整体结构如下所示:

minValues := list with n infinity entries
for i from 0 to n-1
    for every choice c that is a suffix of input[0..i]
        if i - len(c) < 0
            newVal = 1
        else
            newVal = minValues[i - len(c)] + 1
        end if
        if(newVal < minValues[i])
            minValues[i] = newVal
            //optionally record the used chunk
        end if
    next
next

整个字符串的最小块数是 ln-1。可以通过列表回溯得到实际的chunk(需要记录使用过的chunk)。

可以使用(反向选择字符串的)trie 加快检索作为后缀的选择。最坏情况的复杂度仍然是O(n * c * lc)，其中n是输入字符串的长度，c是选择的数量，lc 是选择的最大长度。但是，这种复杂性只会发生在嵌套后缀的选择中(例如 0、10、010、0010 ...)。在这种情况下，trie 将退化为列表。平均而言，运行时间应该少得多。假设从 trie 中检索到的选择数始终是一个小常数，它是 O(n * lc)(实际上，lc 因子可能也更小).

这是一个例子:

choices = ["0","1","10","100"]
text = "10010"

algorithm step    content of minValues
                   0      1       2        3      4
---------------------------------------------------------
initialize        (∞,     ∞ ,     ∞ ,      ∞ ,    ∞     )
i = 0, c = "1"    (1 "1", ∞ ,     ∞ ,      ∞ ,    ∞     )
i = 1, c = "0"    (1 "1", 2 "0",  ∞ ,      ∞ ,    ∞     )
i = 1, c = "10"   (1 "1", 1 "10", ∞ ,      ∞ ,    ∞     )
i = 2, c = "0"    (1 "1", 1 "10", 2 "0",   ∞ ,    ∞     )
i = 2, c = "100"  (1 "1", 1 "10", 1 "100", ∞ ,    ∞     )
i = 3, c = "1"    (1 "1", 1 "10", 1 "100", 2 "1", ∞     )
i = 4, c = "0"    (1 "1", 1 "10", 1 "100", 2 "1", 3 "0" )
i = 4, c = "10"   (1 "1", 1 "10", 1 "100", 2 "1", 2 "10")

含义:我们可以用 2 个 block 组成字符串。追溯以相反的顺序给出 block :“10”、“100”。

关于python - 如何将文本分成 block 最小化解决方案？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39750879/