同じリスト内の別の大きな文字列の一部である場合に文字列を結合する

Question

リストに含まれる可能性のある文と単語のリストがリストから除外され、それらを最大の文字列にマージしたいもし存在するならば。この最大の文字列の「一部」の各出現は、最大の文字列出現回数にカウントされるべきです。

from collections import defaultdict 

sentence_parts = ['quick brown', 'brown fox', 'fox', 'lazy dog', 
        'quick brown fox jumps over the lazy dog',] 

sentences_with_count = defaultdict(int) 

for s in sentence_parts: 
    matching_sentences = sorted([si for si in sentence_parts if s in si and len(si) > len(s)], 
           key=len, reverse=True) 
    if matching_sentences: 
     current_sent_count = sentences_with_count.get(s, 1) 
     sentences_with_count[matching_sentences[0]] += current_sent_count 
    else: 
     sentences_with_count[s] += 1 

print(sentences_with_count) 

のでsentences_with_countの出力は次のようになります。

{ 
    'quick brown fox jumps over the lazy dog': 5 
} 

は、ここで私は、これがすべてでは効率的ではない理解repl.it

です。どうすれば改善できますか？

いくつかのより多くの例：

sentence_parts = ['The', 'Ohio State', 'Ohio', 
        'Paris, France', 'Paris', 
        'The Ohio State University'] 

>>> {'The Ohio State University': 4, 'Paris, France': 2} 

sentence_parts = ['Obama', 'Barack', 'Barack Hussein Obama'] 

>>> {'Barack Hussein Obama': 3} 

sentence_parts = ['Obama', 'Barack', 'Barack Hussein Obama', 
        'Steve', 'Jobs', 'Steve Jobs', 'Mark', 'Bob'] 

>>> {'Barack Hussein Obama': 3, 'Steve Jobs': 3, 'Mark': 1, 'Bob': 1} 

このアプローチのもう一つの問題：部分文字列に対して複数のマッチした文字列がある場合は、最大の唯一のカウントがインクリメントされます。

sentence_parts = ['The', 'The New York City', 'The Voice'] 
>>> {'The New York City': 2, 'The Voice': 1} 

理想的には、出力は{'The New York City': 2, 'The Voice': 2}

Answer 1

である必要があります。これはやや短く、最後に説明されている問題を最大増分のみで修正します。

sentence_parts = ['The', 'Ohio State', 'Ohio', 
       'Paris, France', 'Paris', 
       'The Ohio State University'] 
matching = {key:{'count':1, 'in': False} for key in sentence_parts} 

for i in sentence_parts: 
    for i2 in sentence_parts: 
     if i in i2 and i != i2: 
      matching[i2]['count'] += 1 
      matching[i]['in'] = True 

print({x: matching[x]['count'] for x in matching if not matching[x]['in']}) 

編集：それは編集2

必要はありませんでしたのでが

sentence_parts = sorted(sentence_parts, key=len) 

を削除：リスト内包を使って辞書作成を短縮。

Answer 2

次のソリューションは、2つの操作に概念的問題を分割し、

1. は、すべての文の出現の実際のカウントを検索します。
2. 既に大きな文で計算された文を削除します。

このソリューションは、今後、デバッグして拡張する方が簡単です。

from collections import defaultdict 

sentence_parts = ['The', 'Ohio State', 'Ohio', 
        'Paris, France', 'Paris', 
        'The Ohio State University'] 

sentences_with_count = defaultdict(int) 
for part in sentence_parts: 
    for sentence in sentence_parts: 
     if part in sentence: 
      sentences_with_count[sentence] += 1 

# sentences_with_count contains values for all parts. 
# Next step is to filter the ones counted in bigger terms 

sentence_keys = list(sentences_with_count.keys()) 
for k in sentence_keys: 
    for other in sentence_keys: 
     if k in other and k != other: 
      sentences_with_count.pop(k,None) # Remove consumed terms 
      break 

print(sentences_with_count)