特定のキーワードの文字をまとめて文字列からPythonリストを作成できますか？

Question

文字列内の文字からリストを作成したいが、特定のキーワードをまとめておきたい。例えば

：

キーワード：車、バス

INPUT：

"xyzcarbusabccar" 

OUTPUT：re.findallで

["x", "y", "z", "car", "bus", "a", "b", "c", "car"] 

Answer 1

。あなたのキーワードを最初に置き換えてください。

>>> import re 
>>> s = "xyzcarbusabccar" 
>>> re.findall('car|bus|[a-z]', s) 
['x', 'y', 'z', 'car', 'bus', 'a', 'b', 'c', 'car'] 

キーワードを重複している場合は、このソリューションは、あなたが遭遇する最初の1見つけることに注意してください：あなたは何が好きで[a-z]一部を置換することにより、ソリューションは、より一般的にすることができ

>>> s = 'abcaratab' 
>>> re.findall('car|rat|[a-z]', s) 
['a', 'b', 'car', 'a', 't', 'a', 'b'] 

を、例えば\w、またはいずれかの文字に一致するように単純な.を入力します。

なぜこの作品、なぜ正規表現'[a-z]|car|bus'は動作しません短い説明： 正規表現エンジンは、左から右に交互オプションをしようと試合を返すために、「熱心」です。つまり、オプションの1つが完全に一致するとすぐに、すべての代替案が一致すると見なします。この時点では、残りのオプションのいずれも試行しませんが、処理を停止し、すぐに一致を報告します。 '[a-z]|car|bus'を使用すると、文字クラス[a-z]の文字が見つかるとエンジンは一致を報告し、 'car'または 'bus'も一致するかどうかを確認することはありません。

Answer 2

s = "xyzcarbusabccar" 
import re 

print re.findall("bus|car|\w", s) 
['x', 'y', 'z', 'car', 'bus', 'a', 'b', 'c', 'car'] 

それとも任意の空白以外の文字のための\S：

s = "xyzcarbusabccar!" 
import re 

print re.findall("bus|car|\S", s) 
['x', 'y', 'z', 'car', 'bus', 'a', 'b', 'c', 'car', '!'] 

はちょうどあなたが最も長いマッチをしたい場合は、最初に長い単語を置くためには、正しい取得することを確認してください。

In [7]: s = "xyzcarsbusabccar!" 

In [8]: re.findall("bus|car|cars|\S", s) 
Out[8]: ['x', 'y', 'z', 'car', 's', 'bus', 'a', 'b', 'c', 'car', '!'] 

In [9]: re.findall("bus|cars|car|\S", s) 
Out[9]: ['x', 'y', 'z', 'cars', 'bus', 'a', 'b', 'c', 'car', '!'] 

Answer 3

上記の解決策は本当に素晴らしいですが、キーワード辞書が長い場合、それは簡単に（おそらく実現不可能に）なります。

私は、キーワードをツリー（冗長性を利用する）に格納することを提案しており、より効率的です。

キーワードが["art,"at","atm","bus","can","car"]している場合、辞書は、描画する方が簡単だったので、私はそれがバイナリ作っこの

    . 
       ^
      / ¦  \ 

     / ¦  \ 
     a  b   c 
     ^ ^  ^
    / \  \   \ 
    r  t  u   a 
    ^ ^ ^  ^
/ /\  \  / \ 
    t  m /0  s  n  r 
^ ^  ^ ^ ^
/ /   \  \  \ 
/0  /0    /0  /0 /0 

のように見えます。ノード"/0"は単語終端（仮想キャラクタ）の意味を持ち、"."がルートです。

私たちは最後に、我々は、キーワードを入力し検索この

keywords = ["car","at","atm","bus"] 
keywordsTree = Tree('') 

for keyword in keywords: 
    keywordsTreeNode = keywordsTree 
    for character in keyword: 
     if not keywordsTreeNode.has_child(character): 
      keywordsTreeNode.add_child(Tree(character)) 
     keywordsTreeNode = keywordsTreeNode.get_child(character) 

    keywordsTreeNode.add_child(Tree('/0')) 

のようなコードを使用して構造を構築することができ、キーワードを考える

class Tree(object): 

    def __init__(self, name='root', children=None): 
     self.name = name 
     self.children = {} 
     if children is not None: 
      for child in children: 
       self.add_child(child.name,child) 

    def __repr__(self): 
     return self.name 

    def add_child(self, node): 
     assert isinstance(node, Tree) 
     self.children[node.name] = node 


    def has_child(self,name): 
     return name in self.children 

    def get_child(self,name): 
     return self.children[name] 

    def print_tree(self,level=0): 
     sys.stdout.write('-' * level) 
     print self.name 
     for childTag in self.children: 
      self.children[childTag].print_tree(level+1) 

ツリーと必要な機能を構築するために、この簡単なTreeクラスを実装しました。以下の解決策は、その位置から開始して一致するすべてのキーワードを入力内の所定の位置に提供する。

inputWords = "xyzcarbusabccar8hj/0atm" 
output = [] 
lengthInput = len(inputWords) 
for position in range(0,lengthInput): 
    ##add by default the character 
    # allMathcedKeyWords = [inputWords[position]] 

    allMathcedKeyWords = [] 
    keywordsTreeNode = keywordsTree 
    searchPosition = position 
    curMathcedWord = '' 

    while searchPosition < lengthInput and keywordsTreeNode.has_child(inputWords[searchPosition]) : 

     keywordsTreeNode = keywordsTreeNode.get_child(inputWords[searchPosition]) 
     curMathcedWord = curMathcedWord + inputWords[searchPosition] 

     if (keywordsTreeNode.has_child("/0")): 
      allMathcedKeyWords.append(curMathcedWord) 

     searchPosition += 1 

    if len(allMathcedKeyWords)==0: 
     allMathcedKeyWords = inputWords[position] 

    output.append(allMathcedKeyWords) 

print output 

このコードは、上記のコードのための重要なこの

['x', 'y', 'z', 
['car'], 
'a', 'r', 
['bus'], 
    'u', 's', 'a', 'b', 'c', 
['car'], 
    'a', 'r', '8', 'h', 'j', '/', '0', 
['at', 'atm'], 
    't', 'm'] 

は言葉の最後に仮想の文字が2つの文字（"/0"）であるという事実であると（たとえ一致することはありません出力します上記で詳述した入力シーケンスに組み合わせが表示されます）。さらに、任意の文字列を処理します（入力およびキーワードの場合は、re.findall()のようにエスケープ文字を導入する必要はありません）

この出力リストから、実行する操作を指定できます。 re.findallの解を求める場合は、位置の最長一致単語（またはキーワードの論理的順序に基づいて）を見つけて、その単語に含まれる文字数を先にジャンプします。

さらに問題を取り上げると、入力内のすべての文字が頂点になり、単語を見つけるとその位置からその一致した単語の最後の文字の後の対応する次の頂点にエッジを追加します。最短経路アルゴリズムを使用すると、上記のソリューションを再度利用できます。このように出力を構造化することで、スペース効率が向上し、より複雑なアルゴリズムが実現します。

例、"acart"得られたグラフは、この

   ______________ 
      ¦    ¦ 
- a -> c -> a -> r -> t -> 
     ¦______________¦ 

複雑分析

Space : longest_word_length * number_of_letters_in_keywords 
     input_length + input_length * input_length (worst case-fully connected graph) 
Time : input_length * longest_word_length 
     input_length + input_length * input_length (worst case-fully connected graph)