Algorithmus zu finden Artikel mit ähnlichem Text

StackOverflow https://stackoverflow.com/questions/246961

Frage

Ich habe viele Artikel in einer Datenbank (mit Titel, Text), ich bin für einen Algorithmus sucht die X am ähnlichsten Artikel, so etwas wie Stack-Überlauf des „Verwandte Fragen“, wenn Sie eine Frage stellen zu finden.

Ich habe versucht, für diese googeln aber nur gefundene Seiten zu anderen „ähnlichen Text“ Fragen, so etwas wie jeden Artikel mit allen anderen zu vergleichen und eine Ähnlichkeit irgendwo gespeichert werden. SO tut dies in „Echtzeit“ auf Text, den ich gerade eingegeben hat.

Wie?

War es hilfreich?

Lösung

bearbeiten Abstand ist kein wahrscheinlicher Kandidat, da es Rechtschreibung / Wort Ordnung sein würde abhängig und viel mehr rechenintensiv als Will führt Sie zu glauben, die Größe und Anzahl der Dokumente erwägen Sie tatsächlich bei der Suche interessiert sein würde.

So etwas wie Lucene ist der Weg zu gehen. Sie indizieren alle Ihre Dokumente, und dann, wenn Sie möchten, um Dokumente finden ähnlich wie bei einem bestimmten Dokument, können Sie Ihr bestimmtes Dokument in eine Abfrage drehen, und den Index suchen. Intern wird Lucene verwenden TF-IDF und einen

Andere Tipps

Es hängt von Ihrer Definition von ähnlich.

Der edit-Abstand Algorithmus der Standard-Algorithmus für (lateinische Sprache) Wörterbuch Vorschläge und kann auf ganzen Texten arbeiten. Zwei Texte sind ähnlich, wenn sie im Grunde die gleichen Worte (eh Buchstaben) in der gleichen Reihenfolge. So sind die folgenden zwei Buchbesprechungen wäre ziemlich ähnlich:

1) "Dies ist ein großartiges Buch"

2) "Das sind keine großen Bücher"

(die Anzahl von Buchstaben zu entfernen, einzufügen, löschen oder ändern, drehen (2) in (1) bezeichnet wird, um die ‚Editierdistanz‘.)

Um dies zu implementieren, würden Sie wollen, jede Kritik programmatisch zu besuchen. Dies ist vielleicht nicht so teuer, wie es klingt, und wenn es zu teuer ist, könnten Sie die comparisions als Hintergrundaufgabe machen und speichern Sie den n-most-similiar in einem Datenbankfeld selbst.

Ein weiterer Ansatz ist etwas von der Struktur der (latein) Sprachen zu verstehen. Wenn Sie (nicht-capitialised oder zitiert) Wörter kurzen Streifen und weisen Gewichte Wörter (oder Präfixe), die gemeinsam oder einzigartig sind, können Sie eine Bayesianesque Vergleich zu tun. Die beiden folgenden Buchbesprechungen könnten simiplied und gefunden werden ähnlich zu sein:

3) „Die Französisch Revolution war bla bla Krieg und Frieden bla bla Frankreich.“ -> Frankreich / Französisch (2) Revolution (1) Krieg (1) Frieden (1) (beachten Sie, dass ein Wörterbuch verwendet wurde, zu kombinieren, Frankreich und Französisch)

4) „Dieses Buch ist bla bla eine Revolution in Französisch Küche.“ -> Frankreich (1) Revolution (1)

Um dies zu implementieren, um die ‚Keywords‘ in einer Bewertung identifizieren möchte, wenn es erstellt wurde / aktualisiert und ähnliche Bewertungen diese Schlüsselwörter in der where-Klausel einer Abfrage (im Idealfall ‚Volltext‘ suchen, wenn die Verwendung zu finden Datenbank unterstützt), vielleicht mit einer Nachbearbeitung der Ergebnisse-Set für Scoring die Kandidaten gefunden.

Bücher auch Kategorien haben - sind Thriller in Frankreich gesetzt ähnlich zu historischen Studien von Frankreich, und so weiter? Meta-Daten über Titel und Text könnten nützlich sein für die Ergebnisse relevant zu halten.

Das Tutorial auf die diesem Link klingt wie es sein kann, was Sie brauchen. Es ist leicht zu folgen und funktioniert sehr gut.

Seine Algorithmus Belohnungen beide gemeinsame Teilstrings und eine gemeinsame Anordnung dieser Teilstrings und so sollten ganz schön Ähnliche Titel auswählen.

Ich schlage vor, zu indizieren Ihre Artikel mit Apache Lucene , ein Hoch Leistung, voll funktionsfähige Textsuchmaschine Bibliothek komplett in Java geschrieben. Es ist eine Technologie für nahezu jede Anwendung geeignet, die Volltextsuche erfordert, insbesondere Cross-Plattform . Sobald indiziert, könnte man leicht in Verbindung stehende Artikel finden.

Ein verwendet gemeinsamer Algorithmus ist das Self-Organizing Map . Es ist eine Art von neuronalen Netzwerk, das Ihre Artikel automatisch kategorisieren wird. Dann können Sie einfach den Ort finden, die ein aktueller Artikel in der Karte ist und alle Artikel in der Nähe davon in Zusammenhang stehen. Der wichtige Teil des Algorithmus ist, wie würden Sie Vektor Ihre Eingabe quantisieren. Es gibt mehr Möglichkeiten, um mit mit Text zu tun. Sie können Ihr Dokument / title Hash, können Sie Wörter zählen und dass als n-dimensionalen Vektor verwenden, usw. Ich hoffe, das hilft, auch wenn ich für Sie eine Büchse der Pandora auf einer endlosen Reise in AI geöffnet haben.

Das Gleiche gilt für den Vergleich nur auf dem Titel, nicht auf dem Körper Text der Frage, also nur auf eher kurze Strings.

Sie können ihren Algorithmus verwenden (keine Ahnung, wie es aussieht) auf den Titel des Artikels und die Keywords. Wenn Sie mehr CPU-Zeit zu brennen, auch auf den Abstracts Ihres Artikel.

Die Entsendung der Lucene-Vorschlag für die Volltext, aber beachten Sie, dass Java nicht erforderlich ist; einer .NET-Port verfügbar ist . Siehe auch die Haupt Lucene für Links zu anderen Projekten, einschließlich Lucy, eine C-Port .

Vielleicht, was Sie suchen ist etwas, das paraphrasieren . Ich habe nur oberflächliche Kenntnis davon, aber Umschreibungen ist ein Verarbeitung natürlicher Sprache Konzept, um zu bestimmen, ob zwei Textpassagen eigentlich bedeuten die gleiche Sache -. obwohl die ganz andere Worte verwenden

Leider weiß ich nicht von Werkzeugen, die Sie erlauben, dies zu tun (obwohl ich eine bei der Suche nach interessiert sein würde)

Sie SQL Server-Volltextindex den Smart Vergleich zu bekommen verwenden können, glaube ich, dass SO einen Ajax-Aufruf verwendet, das bedeutet eine Abfrage, die ähnlichen Fragen zurückzukehren.

Welche Technologien verwenden Sie?

Wenn Sie nach Wörtern suchen, der gleich gewickelt ist, könnten Sie konvertieren soundex und die die soundex Worte zu passen ... für mich gearbeitet

habe ich versucht, eine Methode, aber keine funktioniert well.One kann ein relativ satified Ergebnis wie diese:    Erstens: eine Google SimHash Code für jeden Absatz des gesamten Textes erhalten und speichern sie in databse.    Zweitens: Index für den SimHash Code.    Drittens: verarbeiten Ihren Text verglichen, wie oben werden, um ein SimHash Code zu erhalten und den gesamten Text von SimHash Index suchen, die neben einer Hamming-Distanz wie 5-10 bilden. Dann vergleichen simility mit dem Begriff Vektor.   Dies kann arbeitet für große Datenmengen.

Der Link in @ alex77 Antwort zeigt auf einen der Sorensen -dice Coefficient , die unabhängig vom Autor dieses Artikels entdeckt wurde - der Artikel ist sehr gut geschrieben und sehr lesenswert

.

Ich habe mit diesen Koeffizienten für meine eigenen Bedürfnisse endet. Jedoch können die ursprünglichen Koeffizienten zu falschen Ergebnisse führen, wenn Umgang mit

  • Drei-Buchstaben-Wortpaare, die eine misspelling enthalten, z.B. [and,amd] und
  • Drei-Buchstaben-Wort-Paare, die Anagramme sind z.B. [and,dan]

Im ersten Fall Dice irrtümlicherweise einen Koeffizienten von null, während im zweiten Fall meldet der Koeffizient auf, als 0,5 Umdrehungen, die misleadingly hoch ist.

Eine Verbesserung 

function wordPairCount(word)
{
 var i,rslt = [],len = word.length - 1;
 for(i=0;i < len;i++) rslt.push(word.substr(i,2));
 if (2 == len) rslt.push(word[0] + word[len]);
 return rslt;
}

function pairCount(arr)
{
 var i,rslt = [];
 arr = arr.toLowerCase().split(' ');
 for(i=0;i < arr.length;i++) rslt = rslt.concat(wordPairCount(arr[i]));
 return rslt;
}

function commonCount(a,b)
{
 var t;
 if (b.length > a.length) t = b, b = a, a = t; 
 t = a.filter(function (e){return b.indexOf(e) > -1;});
 return t.length;
}

function myDice(a,b)
{
 var bigrams = [],
 aPairs = pairCount(a),
 bPairs = pairCount(b);
 debugger;
 var isct = commonCount(aPairs,bPairs);
 return 2*commonCount(aPairs,bPairs)/(aPairs.length + bPairs.length); 
}

$('#rslt1').text(myDice('WEB Applications','PHP Web Application'));
$('#rslt2').text(myDice('And','Dan'));
$('#rslt3').text(myDice('and','aMd'));
$('#rslt4').text(myDice('abracadabra','abracabadra'));
*{font-family:arial;}
table
{
 width:80%;
 margin:auto;
 border:1px solid silver;
}

thead > tr > td
{
 font-weight:bold;
 text-align:center;
 background-color:aqua;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.0.0/jquery.min.js"></script>
<table>
<thead>
<tr>
<td>Phrase 1</td>
<td>Phrase 2</td>
<td>Dice</td>
</tr>
<thead>
<tbody>
<tr>
<td>WEB Applications</td>
<td>PHP Web Application</td>
<td id='rslt1'></td>
</tr>
<tr>
<td>And</td>
<td>Dan</td>
<td id='rslt2'></td>
</tr>
<tr>
<td>and</td>
<td>aMd</td>
<td id='rslt3'></td>
</tr>
<tr>
<td>abracadabra</td>
<td>abracabadra</td>
<td id='rslt4'></td>
</tr>
</tbody>
</table>

Beachten Sie die absichtliche falsche Schreibweise im letzten Beispiel: Abraca dabra vs Abraca Badra . Auch wenn keine zusätzliche Bigramm Korrektur des Koeffizienten berichtet angewendet wird, ist 0,9. Mit der Korrektur wäre es 0,91 gewesen sein.

Hoffentlich werden andere helfen, die in diesen Thread ausgeführt werden.

ein Beispieltext gegeben, listet das Programm die Repository-Texte nach Ähnlichkeit sortiert: einfache Implementierung Tasche von Wörtern in C ++ . Der Algorithmus ist linear in der Gesamtlänge des Beispieltextes und die Repository-Texte. Außerdem ist das Programm mit mehreren Threads Repository Texte parallel zu verarbeiten.

Hier ist der Kern-Algorithmus: 

class Statistics {
  std::unordered_map<std::string, int64_t> _counts;
  int64_t _totWords;

  void process(std::string& token);
public:
  explicit Statistics(const std::string& text);

  double Dist(const Statistics& fellow) const;

  bool IsEmpty() const { return _totWords == 0; }
};

namespace {
  const std::string gPunctStr = ".,;:!?";
  const std::unordered_set<char> gPunctSet(gPunctStr.begin(), gPunctStr.end());
}

Statistics::Statistics(const std::string& text) {
  std::string lastToken;
  for (size_t i = 0; i < text.size(); i++) {
    int ch = static_cast<uint8_t>(text[i]);
    if (!isspace(ch)) {
      lastToken.push_back(tolower(ch));
      continue;
    }
    process(lastToken);
  }
  process(lastToken);
}

void Statistics::process(std::string& token) {
  do {
    if (token.size() == 0) {
      break;
    }
    if (gPunctSet.find(token.back()) != gPunctSet.end()) {
      token.pop_back();
    }
  } while (false);
  if (token.size() != 0) {
    auto it = _counts.find(token);
    if (it == _counts.end()) {
      _counts.emplace(token, 1);
    }
    else {
      it->second++;
    }
    _totWords++;
    token.clear();
  }
}

double Statistics::Dist(const Statistics& fellow) const {
  double sum = 0;
  for (const auto& wordInfo : _counts) {
    const std::string wordText = wordInfo.first;
    const double freq = double(wordInfo.second) / _totWords;
    auto it = fellow._counts.find(wordText);
    double fellowFreq;
    if (it == fellow._counts.end()) {
      fellowFreq = 0;
    }
    else {
      fellowFreq = double(it->second) / fellow._totWords;
    }
    const double d = freq - fellowFreq;
    sum += d * d;
  }
  return std::sqrt(sum);
}

Die einfachste und schnellste Art und Weise Ähnlichkeit zwischen Abstracts zu vergleichen, ist wahrscheinlich durch das Set-Konzept verwendet. Zuerst konvertiert abstrakte Texte in Satz von Worten. Dann überprüfen, wie viel jeder Satz überlappt. Pythons Feature-Set kommt sehr Hand, diese Aufgabe auszuführen. Sie wären überrascht, zu sehen, wie gut diese Methode auf diese „ähnliche / verwandte Papiere“ Optionen gibt von GScholar, ADS, WOS oder Scopus vorgesehen aus vergleicht.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top