给定该字符串的 ngram 来重建输入字符串

Question

给定一个字符串，例如i am a string.

我可以使用该包生成该字符串的 n 元语法nltk，其中 n 根据指定范围变化。

from nltk import ngrams 

s = 'i am a string'

for n in range(1, 3):

    for grams in ngrams(s.split(), n):

        print(grams)

给出输出：

('i',)

('am',)

('a',)

('string',)

('i', 'am')

('am', 'a')

('a', 'string')

有没有办法使用生成的 ngram 的组合来“重建”原始字符串？或者，用下面评论者的话说，有没有一种方法可以将句子分成连续的单词序列，其中每个序列的最大长度为 k（在本例中 k 为 2）。

[('i'), ('am'), ('a'), ('string')]

[('i', 'am'), ('a'), ('string')]

[('i'), ('am', 'a'), ('string')]

[('i'), ('am'), ('a', 'string')]

[('i', 'am'), ('a', 'string')]

这个问题与这个问题类似，但又增加了一层复杂性。

工作解决方案- 改编自此处。

我有一个可行的解决方案，但对于较长的字符串来说它真的很慢。

def get_ngrams(s, min_=1, max_=4):

    token_lst = []

    for n in range(min_, max_):

        for idx, grams in enumerate(ngrams(s.split(), n)):

            token_lst.append(' '.join(grams))

    return token_lst 

def to_sum_k(s):

    for len_ in range(1, len(s.split())+1):

        for i in itertools.permutations(get_ngrams(s), r=len_):

            if ' '.join(i) == s:

                print(i)

to_sum_k('a b c')

Answer 1

编辑：这个答案基于这样的假设：问题是根据 ngram 重建未知的唯一字符串。对于任何对此问题感兴趣的人，我都会将其保留为活动状态。评论中澄清的实际问题的实际答案可以在这里找到。编辑结束一般来说没有。考虑例如情况n = 2和s = "a b a b"。那么你的ngrams将是[("a"), ("b"), ("a", "b"), ("b", "a")]然而，在这种情况下生成这组 ngram 的字符串集将是由以下方式生成的所有字符串：(ab(a|(ab)*a?))|(ba(b|(ba)*b?)或者n = 2, s = "a b c a b d a", 其中"c"和"d"可以在生成字符串中任意排序。例如“abdabc a”也是一个有效的字符串。此外，还会出现与上述相同的问题，任意数量的字符串都可以生成 ngram 集合。话虽这么说，有一种方法可以测试一组 ngram 是否唯一标识一个字符串：将您的字符串集视为非确定性状态机的描述。每个 ngram 可以定义为一个状态链，其中单个字符是转换。作为 ngrams [("a", "b", "c"), ("c", "d"), ("a", "d", "b")] 的示例，我们将构建以下内容状态机：0 ->(a) 1 ->(b) 2 ->(c) 30 ->(c) 3 ->(d) 40 ->(a) 1 ->(d) 5 ->(b) 6现在执行该状态机的确定。如果存在可以从 ngram 重建的唯一字符串，则状态机将具有最长的转换链，该转换链不包含任何循环并包含我们构建原始状态机的所有 ngram。在这种情况下，原始字符串只是该路径的各个状态转换重新连接在一起。否则，存在可以从提供的 ngram 构建的多个字符串。

Answer 2

虽然我之前的答案假设问题是根据 ngram 找到未知字符串，但这个答案将处理找到使用 ngram 构造给定字符串的所有方法的问题。假设允许重复，解决方案相当简单：生成所有可能的数字序列，总和等于原始字符串的长度，且数字不大于n并使用这些序列来创建 ngram 组合：import numpydef generate_sums(l, n, intermediate):    if l == 0:        yield intermediate    elif l < 0:        return    else:        for i in range(1, n + 1):            yield from generate_sums(l - i, n, intermediate + [i])def combinations(s, n):    words = s.split(' ')    for c in generate_sums(len(words), n, [0]):        cs = numpy.cumsum(c)        yield [words[l:u] for (l, u) in zip(cs, cs[1:])]编辑：正如@norok2（感谢您的工作）在评论中 所指出的，使用替代的 cumsum 实现似乎比为此用例提供的实现更快。 结束编辑numpy如果不允许重复，事情就会变得更加棘手。在这种情况下，我们可以使用我之前的答案中定义的非确定性有限自动机，并根据自动机的遍历构建我们的序列：def build_state_machine(s, n):    next_state = 1    transitions = {}    for ng in ngrams(s.split(' '), n):        state = 0        for word in ng:            if (state, word) not in transitions:                transitions[(state, word)] = next_state                next_state += 1            state = transitions[(state, word)]     return transitionsdef combinations(s, n):    transitions = build_state_machine(s, n)    states = [(0, set(), [], [])]    for word in s.split(' '):        new_states = []        for state, term_visited, path, cur_elem in states:            if state not in term_visited:                new_states.append((0, term_visited.union(state), path + [tuple(cur_elem)], []))            if (state, word) in transitions:                new_states.append((transitions[(state, word)], term_visited, path, cur_elem + [word]))        states = new_states   return [path + [tuple(cur_elem)] if state != 0 else path for (state, term_visited, path, cur_elem) in states if state not in term_visited]作为示例，将为字符串生成以下状态机"a b a"：红色连接表示切换到下一个 ngram，需要单独处理（如果在循环中则需要单独处理），因为它们只能遍历一次。