2

テキストとの関係を計算する次の PHP 関数があります。

function check($terms_in_article1, $terms_in_article2) {
    $length1 = count($terms_in_article1); // number of words
    $length2 = count($terms_in_article2); // number of words
    $all_terms = array_merge($terms_in_article1, $terms_in_article2);
    $all_terms = array_unique($all_terms);
    foreach ($all_terms as $all_termsa) {
        $term_vector1[$all_termsa] = 0;
        $term_vector2[$all_termsa] = 0;
    }
    foreach ($terms_in_article1 as $terms_in_article1a) {
        $term_vector1[$terms_in_article1a]++;
    }
    foreach ($terms_in_article2 as $terms_in_article2a) {
        $term_vector2[$terms_in_article2a]++;
    }
    $score = 0;
    foreach ($all_terms as $all_termsa) {
        $score += $term_vector1[$all_termsa]*$term_vector2[$all_termsa];
    }
    $score = $score/($length1*$length2);
    $score *= 500; // for better readability
    return $score;
}

変数$terms_in_articleXは、テキストに現れるすべての単語を含む配列でなければなりません。

20,000 のテキストのデータベースがあると仮定すると、この関数はすべての接続を実行するのに非常に長い時間がかかります。

このプロセスを加速するにはどうすればよいですか? 常に 2 つのテキストのみを比較するのではなく、すべてのテキストを巨大なマトリックスに追加する必要がありますか? コード、できれば PHP でのアプローチがあれば、それは素晴らしいことです。

あなたが私を助けてくれることを願っています。前もって感謝します!

4

5 に答える 5

4

追加時にテキストを分割できます。簡単な例:preg_match_all(/\w+/, $text, $matches);確かに実際の分割はそれほど単純ではありません...しかし、パターンを修正するだけで可能です:)

word_id(int)、text_id(int)、word_count(int) のように、テーブル id(int primary autoincrement)、value(varchar unique)、およびリンク テーブルを作成します。次に、テキストを分割した後、テーブルに新しい値を入力します。

最後に、DB でインデックス付きの整数 (ID) をすばやく操作して、このデータを必要に応じて処理できます。

更新: テーブルとクエリは次のとおりです。

CREATE TABLE terms (
    id int(11) NOT NULL auto_increment, value char(255) NOT NULL,
    PRIMARY KEY  (`id`), UNIQUE KEY `value` (`value`)
);

CREATE TABLE `terms_in_articles` (
    term int(11) NOT NULL, 
    article int(11) NOT NULL, 
    cnt int(11) NOT NULL default '1',
    UNIQUE KEY `term` (`term`,`article`)
);


/* Returns all unique terms in both articles (your $all_terms) */
SELECT t.id, t.value 
FROM terms t, terms_in_articles a 
WHERE a.term = t.id AND a.article IN (1, 2);

/* Returns your $term_vector1, $term_vector2 */
SELECT article, term, cnt 
FROM terms_in_articles 
WHERE article IN (1, 2) ORDER BY article;

/* Returns article and total count of term entries in it ($length1, $length2) */
SELECT article, SUM(cnt) AS total 
FROM terms_in_articles 
WHERE article IN (1, 2) GROUP BY article;

/* Returns your $score wich you may divide by ($length1 / $length2) from previous query */
SELECT SUM(tmp.term_score) * 500 AS total_score FROM 
(
    SELECT (a1.cnt * a2.cnt) AS term_score 
    FROM terms_in_articles a1, terms_in_articles a2 
    WHERE a1.article = 1 AND a2.article = 2 AND a1.term = a2.term
    GROUP BY a2.term, a1.term
) AS tmp;

さて、私は願っています、これは役に立ちますか?タスクを実行するには、最後の 2 つのクエリで十分です。他のクエリは念のためです。確かに、「最も人気のある用語」などの統計をさらに数えることができます...

于 2009-05-23T21:13:01.647 に答える
1

これは、元の関数のわずかに最適化されたバージョンです。まったく同じ結果が得られます。(ウィキペディアの2つの記事で、10000以上の用語を使用して実行し、それぞれ20回実行します。

check():
test A score: 4.55712524522
test B score: 5.08138042619
--Time: 1.0707

check2():
test A score: 4.55712524522
test B score: 5.08138042619
--Time: 0.2624

コードは次のとおりです。

function check2($terms_in_article1, $terms_in_article2) {
    $length1 = count($terms_in_article1); // number of words
    $length2 = count($terms_in_article2); // number of words

    $score_table = array();
    foreach($terms_in_article1 as $term){
        if(!isset($score_table[$term])) $score_table[$term] = 0;
        $score_table[$term] += 1;
    }
    $score_table2 = array();
    foreach($terms_in_article2 as $term){
        if(isset($score_table[$term])){
            if(!isset($score_table2[$term])) $score_table2[$term] = 0;
            $score_table2[$term] += 1;
        }
    }
    $score =0;
    foreach($score_table2 as $key => $entry){
        $score += $score_table[$key] * $entry;
    }
    $score = $score / ($length1*$length2);
    $score *= 500;
    return $score;
}

(ところで、すべての単語を配列に分割するのに必要な時間は含まれていませんでした。)

于 2009-05-27T16:56:35.930 に答える
1

編集:より明確にしようとしています:

  1. まず、すべての項を整数にエンコードします。次のように、辞書連想配列を使用できます。

       $count = 0;
        foreach ($doc as $term) {
          $val = $dict[$term];
          if (!defined($val)) {
            $dict[$term] = $count++;
          }
          $doc_as_int[$val] ++;
        }
    

    このようにして、文字列計算を整数計算に置き換えます。たとえば、「cloud」という単語を数字の 5 として表し、配列のインデックス 5 を使用して「cloud」という単語の数を格納できます。ここでは連想配列検索のみを使用していることに注意してください。CRC などは必要ありません。

  2. すべてのテキストをマトリックス、できればスパースとして保存してください。
  3. 機能選択 (PDF)を使用します。
  4. おそらく、より高速な言語でネイティブ実装を使用してください。
  5. 最初に約 20 個のクラスターで K-means を使用することをお勧めします。この方法で、どのドキュメントが別のドキュメントに近いかの大まかなドラフトを取得してから、各クラスター内のペアのみを比較します。クラスターのサイズが均一であると仮定すると、これにより、比較の数が20*200 + 20*10*919900 から約 6000 に改善されます。
于 2009-05-23T18:33:22.537 に答える
0

配列の代わりに単純なテキストを使用して比較でき、目標がどこにあるかを正しく理解している場合は、levenshtein php関数を使用できます(これは通常、グーグルのような「Did you mean ...?」関数を与えるために使用されますphp検索エンジンで)。

これは、使用するのとは逆の方法で機能します。2つの文字列の差を返します。

例:

<?php
function check($a, $b) {
    return levenshtein($a, $b);
}

$a = 'this is just a test';
$b = 'this is not test';
$c = 'this is just a test';

echo check($a, $b) . '<br />';
//return 5
echo check($a, $c) . '<br />';
//return 0, the strings are identical
?>

しかし、これによって実行速度が向上するかどうかは正確にはわかりません。しかし、おそらくそうです。多くのforeachループとarray_merge関数を削除します。

編集:

速度の簡単なテスト(30秒の書き込みスクリプトであり、100%正確ではありません):

function check($terms_in_article1, $terms_in_article2) {
    $length1 = count($terms_in_article1); // number of words
    $length2 = count($terms_in_article2); // number of words
    $all_terms = array_merge($terms_in_article1, $terms_in_article2);
    $all_terms = array_unique($all_terms);
    foreach ($all_terms as $all_termsa) {
        $term_vector1[$all_termsa] = 0;
        $term_vector2[$all_termsa] = 0;
    }
    foreach ($terms_in_article1 as $terms_in_article1a) {
        $term_vector1[$terms_in_article1a]++;
    }
    foreach ($terms_in_article2 as $terms_in_article2a) {
        $term_vector2[$terms_in_article2a]++;
    }
    $score = 0;
    foreach ($all_terms as $all_termsa) {
        $score += $term_vector1[$all_termsa]*$term_vector2[$all_termsa];
    }
    $score = $score/($length1*$length2);
    $score *= 500; // for better readability
    return $score;
}


$a = array('this', 'is', 'just', 'a', 'test');
$b = array('this', 'is', 'not', 'test');

$timenow = microtime();
list($m_i, $t_i) = explode(' ', $timenow);

for($i = 0; $i != 10000; $i++){
    check($a, $b);
}
$last = microtime();
list($m_f, $t_f) = explode(' ', $last);
$fine = $m_f+$t_f;
$inizio = $m_i+$t_i;
$quindi = $fine - $inizio;
$quindi = substr($quindi, 0, 7);
echo 'end in ' . $quindi . ' seconds';

印刷:0.36765秒で終了

2番目のテスト:

<?php
function check($a, $b) {
    return levenshtein($a, $b);
}

$a = 'this is just a test';
$b = 'this is not test';

$timenow = microtime();
list($m_i, $t_i) = explode(' ', $timenow);
for($i = 0; $i != 10000; $i++){
    check($a, $b);
}
$last = microtime();
list($m_f, $t_f) = explode(' ', $last);
$fine = $m_f+$t_f;
$inizio = $m_i+$t_i;
$quindi = $fine - $inizio;
$quindi = substr($quindi, 0, 7);
echo 'end in ' . $quindi . ' seconds';
?>

印刷:0.05023秒で終了

だから、はい、速く見えます。多くの配列アイテム(およびレーベンシュタインの多くの単語)を試してみるといいでしょう

2°編集

同様のテキストでは、速度はレーベンシュタイン法と同じように見えます。

<?php
function check($a, $b) {
    return similar_text($a, $b);
}

$a = 'this is just a test ';
$b = 'this is not test';

$timenow = microtime();
list($m_i, $t_i) = explode(' ', $timenow);
for($i = 0; $i != 10000; $i++){
    check($a, $b);
}
$last = microtime();
list($m_f, $t_f) = explode(' ', $last);
$fine = $m_f+$t_f;
$inizio = $m_i+$t_i;
$quindi = $fine - $inizio;
$quindi = substr($quindi, 0, 7);
echo 'end in ' . $quindi . ' seconds';
?>

印刷:0.05988秒で終了

ただし、255文字以上かかる場合があります。

このアルゴリズムの複雑さはO(N ** 3)であることに注意してください。ここで、Nは最長の文字列の長さです。

また、類似性の値をパーセンテージで返すこともできます。

function check($a, $b) {
    similar_text($a, $b, $p);
    return $p;
}

さらに別の編集

すべてのデータを取得してループするのではなく、SQLクエリで直接比較するために、データベース関数を作成するのはどうですか?

Mysqlを実行している場合は、これを見てください(手作りのレーベンシュタイン関数、まだ255文字の制限)。そうでない場合は、Postgresqlを使用している場合は、この他の関数(評価する必要のある多くの関数)

于 2009-05-26T14:17:31.473 に答える
0

採用すべきもう 1 つのアプローチは、潜在的セマンティック分析です。これは、大量のデータ コーパスを活用してドキュメント間の類似点を見つけます。

それが機能する方法は、テキストの共起マトリックスを取得し、それをコーパスと比較することであり、本質的に「意味空間」でのドキュメントの抽象的な場所を提供します。これにより、LSA セマンティック スペースでユークリッド距離を使用してドキュメントを比較できるため、テキスト比較が高速化されます。セマンティック インデックス作成はとても楽しいものです。したがって、新しい記事を追加するのにそれほど時間はかかりません。

学校で学んだだけなので、このアプローチの具体的な使用例を示すことはできませんが、KnowledgeSearch はアルゴリズムのオープン ソース実装のようです。

(すみません、初めての投稿なので、リンクを投稿できません。調べてみてください)

于 2009-06-01T14:14:24.463 に答える