4

テキストのチャンク内の文字列の出現回数をカウントするための最も効率的な (または一般的に使用される) アルゴリズムは何かに興味があります。

私が読んだことによると、Boyer-Moore 文字列検索アルゴリズムは文字列検索の標準ですが、出現回数を効率的にカウントすることが文字列を検索することと同じかどうかはわかりません。

Pythonでは、これが私が欲しいものです:

text_chunck = "one two three four one five six one"
occurance_count(text_chunck, "one") # gives 3.

編集: python がそのようなstr.count方法として機能するようです。ただし、使用するアルゴリズムを見つけることができません。

4

3 に答える 3

3

まず第一に、Boyer-Moore を使用すると非常に効率的にこれを実現できます。ただし、問題の他のパラメーターによっては、より良い解決策がある場合があります。

Aho-Corasick 文字列マッチング アルゴリズムは、ターゲット文字列内のパターン文字列のセットのすべての出現を検出し一致するすべてのパターンの長さ、および z は生成された一致の総数です。一致させる文字列が 1 つだけの場合、これはソース文字列とターゲット文字列のサイズに比例します。また、同じ文字列が重複して出現することも検出されます。さらに、一連の文字列がソース文字列に何回出現するかを確認したい場合は、アルゴリズムを 1 回呼び出すだけで済みます。これに加えて、検索する文字列のセットが変更されない場合は、前処理時間として O(n) 作業を実行し、O(m + z) ですべての一致を見つけることができます。

一方、1 つのソース文字列と、急速に変化する一連の部分文字列を検索する場合は、サフィックス ツリーを使用することをお勧めします。検索する文字列の O(m) 前処理時間で、部分文字列あたり O(n) 時間で、長さ n の特定の部分文字列が文字列に何回出現するかを確認できます。

最後に、コードを簡単に、最小限の手間で作成できるものを探している場合は、ローリング ハッシュ関数を使用して文字列を検索するRabin-Karpアルゴリズムを検討することを検討してください。これは、およそ 10 ～ 15 行のコードでコーディングでき、前処理時間がなく、通常のテキスト文字列 (多数のテキストで一致がほとんどない) の場合、すべての一致を非常に迅速に見つけることができます。

お役に立てれば！

于 2011-08-26T17:38:15.933 に答える
1

Boyer-Moore は、一度だけ実行する必要があるオーバーヘッドがあるため、出現回数をカウントするのに適しています。パターン文字列が長いほど良いので、「1」の場合は良い選択ではありません。

オーバーラップをカウントする場合は、前の一致の 1 文字後に次の検索を開始します。オーバーラップを無視したい場合は、前の一致から完全なパターン文字列の長さの次の検索を開始します。

ある文字列を別の文字列から検索するための indexOf または strpos メソッドが言語にある場合は、それを使用できます。遅いことが判明した場合は、より良いアルゴリズムを選択してください。

于 2010-05-04T19:04:21.603 に答える
-1

Hellnar、単純な辞書を使用して、文字列内の出現回数を数えることができます。アルゴリズムはカウントアルゴリズムです。例を次に示します。

"""
The counting algorithm is used to count the occurences of a character
in a string. This allows you to compare anagrams and strings themselves.
ex. animal, lamina a=2,n=1,i=1,m=1
"""

def count_occurences(str):
  occurences = {}
  for char in str:
    if char in occurences:
      occurences[char] = occurences[char] + 1
    else:
      occurences[char] = 1
  return occurences

  def is_matched(s1,s2):
    matched = True
    s1_count_table = count_occurences(s1)

    for char in s2:
      if char in s1_count_table and s1_count_table[char]>0:
      s1_count_table[char] -= 1
    else:
      matched = False
      break
    return matched

  #counting.is_matched("animal","laminar")

この例では、文字列が一致した場合にTrueまたはFalseを返します。このアルゴリズムは、文字が文字列に現れる回数をカウントすることを覚えておいてください。これはアナグラムに適しています。

于 2011-08-26T17:23:22.497 に答える