-1

* を含む単語のリストのすべての出現を検閲する必要があります。リストには約 400 の単語があり、大量のトラフィックが発生するため、非常に効率的なものにしたいと考えています。これを行うための効率的なアルゴリズム/データ構造は何ですか? できれば、すでに Python にあるもの。

例:

  1. 「腹を立てる」 => 「**** オフ」
  2. 「こんにちは」 => 「こんにちは」
  3. 「地獄に行く」 => 「****に行く」
4

5 に答える 5

1

大文字と小文字を区別しないtrieに基づくセットの実装は、法案に適合する可能性があります。単語ごとに、最小限の文字のみを処理します。たとえば、'zoo' という単語の最初の文字を処理するだけで、その単語がリストに存在しないことがわかります ('z' の罵倒語がない場合)。

ただし、これは python にパッケージ化されていないものです。C で実装されているため、単純な辞書ソリューションのパフォーマンスが向上する場合があります。

于 2012-08-28T03:02:12.227 に答える
0

cheekenが述べたように、aTrieが必要な場合があります。実際には、Aho–Corasick文字列照合アルゴリズムを使用する必要があります。トライ以上のもの。

すべての文字列について、S処理する必要があるとすると、時間計算量は約O(len(S))です。つまり、線形

そして、最初にオートマトンを構築する必要があります。時間計算量はO(sigma(len(words)))であり、空間計算量は約（常にではありません）O(52*sigma(len(words)))ここで52はアルファベットのサイズを意味します（私はそれをとらえます['a'..'z', 'A'..'Z']）。そして、これを1回だけ（またはシステムが起動するたびに）行う必要があります。

于 2012-08-28T13:25:16.250 に答える
0

正規表現ベースのソリューションを他のソリューションと比較したい場合があります。私は以前、テキストの 1 ～ 3,000 語の同様の正規表現ベースの置換を使用して、フレーズをリンクに変更したことがありますが、それらのページを多くの人に提供していません。

一連の単語 (フレーズの場合もあります) を取得し、'\b' があるため、テキスト内の完全な単語としての出現に一致する正規表現を作成します。

単語をサニタイズされたバージョンにマッピングする辞書がある場合は、それを使用できます。ここでは、便宜上、すべての奇数文字を「*」に置き換えています。

サニタイザー関数は、一致した悪口のサニタイズされたバージョンを返すだけであり、サニタイズされたバージョンを返すためにテキストの正規表現置換呼び出しで使用されます。

import re
swearwords = set("Holy Cow".split())
swear = re.compile(r'\b(%s)\b' % '|'.join(sorted(swearwords, key=lambda w: (-len(w), w))))
sanitized = {sw:''.join((ch if not i % 2 else '*' for i,ch in enumerate(sw))) for sw in swearwords}

def sanitizer(matchobj):
    return sanitized.get(matchobj.group(1), '????')

txt = 'twat prick Holy Cow ... hell hello shitter bonk'
swear.sub(sanitizer, txt)
# Out[1]: 'twat prick H*l* C*w ... hell hello shitter bonk'

re.subn と count 引数を使用して、行われる置換の数を制限し、冒とく的な表現が多すぎる場合はテキスト全体を拒否することをお勧めします。

maxswear = 2
newtxt, scount = swear.subn(sanitizer, txt, count=maxswear)
if scount >= maxswear: newtxt = 'Ouch my ears hurt. Please tone it down' 
print(newtxt)
# 'Ouch my ears hurt. Please tone it down'
于 2012-08-28T07:04:32.827 に答える
0

(1) P を検閲するフレーズの集合とする。

(2) 事前計算 H = {h(w) | p in P、w は p} の単語です。ここで、h は適切なハッシュ関数です。

(3) 入力された単語 v ごとに、H に h(v) があるかどうかをテストします。

(4) h(v) が H にない場合、v を発行します。

(5) H の h(v) の場合、v とそれに続く単語が P の句を形成するかどうかを確認する単純な方法に戻ります。

ステップ (5) は、入力量に比べて P が (非常に) 小さいと仮定しているため、問題ではありません。ステップ (3) は O(1) 操作です。

于 2012-08-28T03:44:12.243 に答える
-1

パフォーマンスが必要な場合は、次のことをお勧めします。

  • 入力のサンプルを取得する
  • 1 行あたりの検閲された単語の平均量を計算する
  • 行ごとにフィルターする単語の最大数を定義します (例: 3)
  • サンプルでヒット数が最も多い検閲された単語を計算する
  • 検閲された単語を指定すると、IF ステートメントを含む Python ファイルを生成して各単語をチェックし、「最もヒットした」単語を最初に配置する関数を作成します。これは、単語全体を一致させたいだけなので、かなり単純です。
  • 1行あたりの最大数に達したら、関数を終了します

私はこれが良くないことを知っています.トラフィックが多いシナリオのためにこのアプローチを提案しているだけです.リスト内の各単語のループを実行すると、パフォーマンスに大きな悪影響を及ぼします.

問題に取り組む方法について、助けになるか、少なくともすぐに使えるアイデアを提供してくれることを願っています。

于 2012-08-28T03:09:22.843 に答える