給定一個字符串，例如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')
2 回答
溫溫醬
TA貢獻1752條經驗 獲得超4個贊
編輯：
這個答案基于這樣的假設：問題是根據 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) 3
0 ->(c) 3 ->(d) 4
0 ->(a) 1 ->(d) 5 ->(b) 6
現在執行該狀態機的確定。如果存在可以從 ngram 重建的唯一字符串，則狀態機將具有最長的轉換鏈，該轉換鏈不包含任何循環并包含我們構建原始狀態機的所有 ngram。在這種情況下，原始字符串只是該路徑的各個狀態轉換重新連接在一起。否則，存在可以從提供的 ngram 構建的多個字符串。
12345678_0001
TA貢獻1802條經驗 獲得超5個贊
雖然我之前的答案假設問題是根據 ngram 找到未知字符串，但這個答案將處理找到使用 ngram 構造給定字符串的所有方法的問題。
假設允許重復，解決方案相當簡單：生成所有可能的數字序列，總和等于原始字符串的長度，且數字不大于n并使用這些序列來創建 ngram 組合：
import numpy
def 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 transitions
def 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，需要單獨處理（如果在循環中則需要單獨處理），因為它們只能遍歷一次。
添加回答
舉報
0/150
提交
取消