文字列セット内の相互包含関係アルゴリズム

文字列セット内の相互包含関係アルゴリズム
まず使用シーンを紹介します.ソースファイルはexcelテーブルで、ある列の値に基づいて正規表現を生成します.正規表現の正確性を保証するために、含まれるデータは正規表現を直接生成できないに違いありません.例えば、産婦人科や産婦人科では、直接正規表現を生成すると、すべての産婦人科がマッチングすべき文字列は産科でマッチングできるので、文字列配列全体を相互に含む関係を検証するpython実装アルゴリズムが必要になる.
代替アルゴリズム:

単純遍歴

は、

を長さで並べ替える.

は、まず1つの文字列

に結合される.
単純な遍歴
紹介:この紹介が一番簡単なのは、単純に文字列配列を遍歴し、現在の文字列Aがその後ろの任意の文字列と包含関係があるか否か(双方向判断)を判断し、長さが短いものは必ず長さが長いものを含んではいけないので、一度判断すればよい、また、双方向判断なので、だから毎回比較だけで後に位置する利点:簡単な欠点を実現する:遅い、特に遅い、文字列の数が多いほど、効率の乗算が低下する
長さで並べ替えてから巡回する
紹介:長さ別にソートするか、長さ別に分類するのが適切で、文字列の長さによって、ソース文字列の集合をいくつかの集合に分け、事前にすべてのデータが重複していないことを確定する必要があります.それから、長さの短いデータの集合を遍歴して、長さの長い集合の中のデータに含まれる利点を判断することができます:簡単な遍歴よりやや速く、すべての双方向の判断部分を最適化して、毎回どの長さがもっと長いかを判断するのは間違いなく時間の欠点です:やはり速くなくて、効率の大きい長さはデータの長さの分布にかかって、例えば長さが2と長さが3のデータだけあって、それでは2里の面のデータが3の中のデータに含まれているかどうかを判断するだけでいいです
まず文字列にマージ
紹介:このアルゴリズムはpython内部の検索アルゴリズムの効率に大きく依存しています(実際には各アルゴリズムがこのfind、またはcountメソッドを呼び出します).まず、すべての文字列配列を1つの文字列につなぎ、区切り記号で分けます.区切り記号の区切りの目的は、前の文字列の後半に後の文字列の前半を加えてある文字列が含まれている場合を避けるために文字列配列を巡り、次にこのつづり文字列が各文字列を含む回数が1を超えるか否かを判断するだけでよい、1を超えると、この文字列が他の文字列に含まれる利点が説明されます.前の2つのアルゴリズムを比較すると、このアルゴリズムの効率の向上は間違いなく倍増し、各文字列の判断はfindまたはcountメソッドを1回だけ呼び出し、複数回の欠点ではありません.あるいは、向上させるべきは実はその限界です.効率はpython内部で実現される検索アルゴリズムの効率に依存する.また、他の2つのアルゴリズムはfindまたはcountを呼び出すたびに文字列が単一の文字列であり、比較的短い.何度も呼び出されたが、このアルゴリズムは文字列ごとに1回しか呼び出さなかったが、つなぎ合わせる文字列の長さは非常に長い.だからこれも昇格すべきところ昇格案です:ここの昇格案は、現在の状況にのみ適用され、需要の背景から知ることができます.実は、ここでは含まれている文字列の集合を返すだけでいいので、接合文字列に文字列が含まれている回数が1より大きいと判断すれば、countメソッドを呼び出さないだけです.そうすると、スペル文字列全体を遍歴して結果を返す必要があります.findを使用する必要があります.そして、自分で書き直したfindです.findの役割は、最初の一致項目を見つけて、位置を返すことです.私たちは2番目の戻りを見つけることができます.そうしないと、-1を返します.そうすれば、スペル文字列に2回の文字列が含まれていることがわかりました.私たちは直接返すことができて、毎回すべてつなぎ文字列を遍歴する必要はありません.同様に、さらに最適化するために、私たちは長さによって並べ替えてからつなぎを行うことができて、できるだけ早く帰って2回目の更新の夜にクラスのバスの上で考えたことを保証して、上述の昇格案は実はまだ一定の問題があって、探すスピードは固定していません.含まれる項目と含まれる項目の位置が不確定であるため、次に考える最適化案は、長さに基づいて並べ替え、長さを前にしてから、現在の文字列よりも長い値からなる文字列が現在の文字列を一度含んでいるか否かを判断するだけでよいので、findアルゴリズムを書き換える必要がなく、また、並べ替え時に、文字列を挿入するたびに各長さの位置を記録するために単独の変数を採用することができ、そうすると挿入は直接適切な位置に位置決めして挿入することができ、コードを判断するたびに単純な3種類目のコードしか与えられなくなり、昇格案はビッグデータ量での最適化に向けられ、私のツールには適用性が強くなく、構想だけを与えて、コードを書かない.暇があれば書き直す

#       ，                
def isContain(dataStr):
    global splitSign
    #      ，            
    baoHanList = []
    #     ，            
    otherList = []
    #          
    for childData in dataStr[len(splitSign):].split(splitSign):
        #        
        if -1 !=dataStr.find(childData, dataStr.find(childData) + 1):
            baoHanList.append(childData)
        else:
            otherList.append(childData)
    return {"baoHanList":baoHanList,"otherList":otherList}
... prompt'''

まとめ:
まとめて、まあ、最後の1種が最も速くて、それから最適化の構想を提供して、コードを提供していないで、後で暇があって更に穴を埋めます