1

文字の順序を変更せずに、文字列を可能なすべての方法に分割する必要があります。このタスクは、NLP のトークン化または見出し語化と見なすことができることを理解していますが、より単純で堅牢な純粋な文字列検索の観点から試みています。与えられた、

dictionary = ['train','station', 'fire', 'a','trainer','in']
str1 = "firetrainstation"

タスク 1: 次のようなすべての可能な部分文字列を生成するにはどうすればよいですか。

all_possible_substrings = [['f','iretrainstation'],
['fo','retrainstation'], ...
['firetrainstatio','n'],
['f','i','retrainstation'], ... , ...
['fire','train','station'], ... , ...
['fire','tr','a','instation'], ... , ...
['fire','tr','a','in','station'], ... , ...
['f','i','r','e','t','r','a','i','n','s','t','a','t','i','o','n']

タスク 2:では、辞書のすべての要素を含む部分文字列セットが正しい出力であることを確認するall_possible_substringにはどうすればよいでしょうか。目的の出力は、左から右に最も多くの文字に一致する辞書の部分文字列のリストです。目的の出力は次のとおりです。

"".join(desire_substring_list) == str1 and \
[i for i desire_substring_list if in dictionary] == len(desire_substring_list)
#(let's assume, the above condition can be true for any input string since my english
#language dictionary is very big and all my strings are human language 
#just written without spaces)

望ましい出力:

'fire','train','station'

私が何をした？

タスク 1については、これを実行しましたが、可能なすべての空白挿入が得られるわけではないことはわかっています。

all_possible_substrings.append(" ".join(str1))

私はこれを行いましたが、これはタスク2のみを行います:

import re
seed = ['train','station', 'fire', 'a','trainer','in']
str1 = "firetrainstation"
all_possible_string = [['f','iretrainstation'],
['fo','retrainstation'],
['firetrainstatio','n'],
['f','i','retrainstation'], 
['fire','train','station'], 
['fire','tr','a','instation'], 
['fire','tr','a','in','station'], 
['f','i','r','e','t','r','a','i','n','s','t','a','t','i','o','n']]
pattern = re.compile(r'\b(?:' + '|'.join(re.escape(s) for s in seed) + r')\b')
highest_match = ""
for i in all_possible_string:
  x = pattern.findall(" ".join(i))
  if "".join(x) == str1 and len([i for i in x if i in seed]) == len(x):
    print " ".join(x)
4

1 に答える 1

3

最初の部分では、次のような再帰ジェネレーターを作成できます。

>>> def all_substr(string):
    for i in range(len(string)):

        if i == len(string) - 1:
            yield string

        first_part = string[0:i+1]
        second_part = string[i+1:]

        for j in all_substr(second_part):
            yield ','.join([first_part, j])


>>> for x in all_substr('apple'):
    print(x)


a,p,p,l,e
a,p,p,le
a,p,pl,e
a,p,ple
a,pp,l,e
a,pp,le
a,ppl,e
a,pple
ap,p,l,e
ap,p,le
ap,pl,e
ap,ple
app,l,e
app,le
appl,e
apple
于 2013-03-19T04:17:31.287 に答える