python 简化ngram循环以压缩给定固定ngram集合的字符串

zpjtge22  于 2023-05-05  发布在  Python
关注(0)|答案(1)|浏览(141)

bounty还有4天到期。回答此问题可获得+50声望奖励。alvas正在寻找一个答案从一个有信誉的来源

在字符列表中给出list('Hello▁world▁')和字符元组列表,即
[('l','l'),('ell','o'),('Hell','o'),('w','or'),('o','r'),('e','l'),('el','l'),('H','ell'),('H','e'),('He','ll '),(' worl ','d '),(' wor ',' l'),('l','d'),('d ',''),(' wor ','ld '),(' H ',' el'),('o',''),('w','o'),(' l ',' o '),(' l ',' o')]
目标是遍历元组,如果匹配,则折叠字符列表。我试过了,它很有效:

import copy

def matcher(s, ngram):
  while s:
    window = tuple(s[:2]) # Since the string tuples are in pairs.
    if window == ngram:
      yield "".join(window)
      s = s[2:]
    else:
      yield s[0]
      s = s[1:]

def combine_ngrams(s, vocab):
  prev = copy.copy(s)
  while True:
    for v in vocab:
      s = list(matcher(s, v))
    if s == prev:
      break
    else:
      prev = s
  return s

vocab = [('l', 'l'), ('ell', 'o▁'), ('Hell', 'o▁'), ('w', 'or'), ('o', 'r'), ('e', 'l'), ('el', 'l'), ('H', 'ell'), ('H', 'e'), 
         ('He', 'll'), ('worl', 'd▁'), ('wor', 'l'), ('l', 'd▁'), ('d', '▁'), ('wor', 'ld▁'), ('H', 'el'), ('o', '▁'), ('w', 'o'), ('l', 'o▁'), ('l', 'o')]

s = list('Hello▁world▁')

combine_ngrams(s, vocab)

[out]:

['Hello▁', 'world▁']

但是外部函数combine_ngrams()和内部函数matcher()中的多个while循环看起来很容易简化。
或者,这些操作不需要遍历元组,也许一些正则表达式方法迭代地应用vocab替换会起作用。有没有办法简化combine_ngrams函数中嵌套的while循环?
下面是更多的输入/输出示例:
[in]:

s = list('abcde'); vocab = [('a', 'b'), ('b', 'c'), ('a', 'bc'), ('abc', 'd'), ('abcd', 'e')]

s = list('abcde'); vocab = [('a', 'b'), ('ab', 'c'), ('b', 'c'),  ('a', 'bc'), ('abc', 'd'), ('abcd', 'e')]

s = list('aaab'); vocab = [('a', 'a'), ('a', 'aa'), ('aaa', 'b')]

s = list('Hello▁ポケモンセンター▁world▁'); vocab = [('l', 'l'), ('ell', 'o▁'), ('Hell', 'o▁'), ('w', 'or'), ('o', 'r'), ('e', 'l'), ('el', 'l'), ('H', 'ell'), ('H', 'e'), ('He', 'll'), ('worl', 'd▁'), ('wor', 'l'), ('l', 'd▁'), ('d', '▁'), ('wor', 'ld▁'), ('H', 'el'), ('o', '▁'), ('w', 'o'), ('l', 'o▁'), ('l', 'o')]

[out]:

['ab', 'c', 'd', 'e']

['abcde']

['aa', 'a', 'b']

['Hello▁', 'ポ', 'ケ', 'モ', 'ン', 'セ', 'ン', 'タ', 'ー', '▁', 'world▁']

P/S:对于任何感兴趣的人,这与byte-pair encoding算法有关,如果有一个更算法的方法而不是Python循环来解决这个问题,请建议。

4ioopgfo

4ioopgfo1#

可以使用纯文本字符串替换来代替正则表达式。
这种方法需要一个从未包含在输入中的分隔符。此外,分隔符不应重复包含相同的序列,以使str.split正常工作。
我还没有提出一个选择适当分隔符的通用算法。但是,出于实用目的,您可以使用Unicode Private Use Area定义一个不能用于输入的字符串(序列)。请注意,您不必禁止使用某些字符,只需禁止使用特定的字符串。

def combine_ngrams2(s, vocab):
    sep = "\uE000"
    ss = "".join(s)
    while sep in ss:
        sep += chr(0xE000 + len(sep))
    assert sep not in ss and len(set(sep)) == len(sep)

    prev = None
    current = f"{sep}{sep.join(s)}{sep}"
    while prev != current:
        prev = current
        for v1, v2 in vocab:
            current = current.replace(f"{sep}{v1}{sep}{v2}{sep}", f"{sep}{v1}{v2}{sep}")

    return current[len(sep) : -len(sep)].split(sep)

这个解决方案看起来像是一个愚蠢的实现,但是str.replace优化得非常好,很难找到更好的替代方案。

相关问题