Wie kann ich feststellen, ob eine zufällige Zeichenfolge wie Englisch klingt?

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

  •  01-07-2019
  •  | 
  •  

Frage

Ich habe einen Algorithmus, die Strings basierend auf einer Liste von Eingangsworten erzeugt. Wie kann ich nur die Saiten trennen, die wie englische Wörter klingt? dh. Verwerfungs RDLO unter Beibehaltung Herr .

EDIT: Um zu klären, die sie benötigen, nicht die tatsächlichen Wörter im Wörterbuch zu sein. Sie müssen nur wie Englisch klingen. Zum Beispiel KEAL würde akzeptiert werden.

War es hilfreich?

Lösung

Sie können eine Markow-Kette eines riesigen Englisch Text bauen.

Danach können Sie Wörter in die Markow-Kette füttern und überprüfen, wie hoch die Wahrscheinlichkeit ist, dass das Wort Englisch ist.

Sehen Sie hier: http://en.wikipedia.org/wiki/Markov_chain

Am Ende der Seite können Sie den markov Textgenerator sehen. Was Sie wollen, ist genau das Gegenteil davon.

Auf den Punkt gebracht: Die Markow-Filialisten für jedes Zeichen die Wahrscheinlichkeiten von denen nächste Zeichen folgen. Sie können diese Idee auf zwei oder drei Zeichen verlängern, wenn Sie über genügend Speicher.

Andere Tipps

Die einfache Art und Weise mit Bayes-Filter (Python Beispiel von http://sebsauvage.net/python/snyppets / # bayesian ) 

from reverend.thomas import Bayes
guesser = Bayes()
guesser.train('french','La souris est rentrée dans son trou.')
guesser.train('english','my tailor is rich.')
guesser.train('french','Je ne sais pas si je viendrai demain.')
guesser.train('english','I do not plan to update my website soon.')

>>> print guesser.guess('Jumping out of cliffs it not a good idea.')
[('english', 0.99990000000000001), ('french', 9.9999999999988987e-005)]

>>> print guesser.guess('Demain il fera très probablement chaud.')
[('french', 0.99990000000000001), ('english', 9.9999999999988987e-005)]

Sie können dies durch eine Kandidatenkette Zeichenüber in Bigrams -Paare von adjascent Buchstaben- und Überprüfung jedes Bigramm gegen eine Tabelle der englischen Bigramm Frequenzen.

  • Ganz einfach: wenn eine Bigramm auf der Frequenztabelle (oder gar nicht vorhanden) ausreichend niedrig ist, lehnt die Zeichenfolge als nicht plausibel. (String enthält einen "QZ" Bigramm? Ablehnen!)
  • Weniger einfach: die allgemeine Plausibilität der gesamten Zeichenfolge berechnen in Bezug auf die, sagen wir, ein Produkt der Frequenzen jedes Bigramm durch die mittlere Frequenz eines gültigen englische Zeichenfolge dieser Länge unterteilt. Dies würde ermöglichen es Ihnen, sowohl (a) unter sonst Hochfrequenz-Bigramme eine Zeichenfolge mit einer ungeraden tieffrequenten Bigramm zu akzeptieren, und (b) lehnen eine Zeichenkette mit mehreren einzelnen Low-aber-nicht-ganz-Below-the-Schwelle Bigrams .

beiden Fällen würde sich eine gewisse Abstimmung der Schwelle erfordern (s), die zweite Technik mehr als die erste.

mit trigrams das gleiches tun würde wahrscheinlich robuste, obwohl es wird wahrscheinlich auch führen zu einem etwas strengen Satz von „gültig“ Strings. Ob das ein Gewinn oder nicht, hängt von Ihrer Anwendung.

Bigramm und Trigrammtabellen basierend auf bestehenden Forschungs Corpora kostenlos oder Kauf zur Verfügung stehen (I fanden keine frei verfügbar, aber haben nur ein oberflächlicher google bisher), aber man kann von sich aus eine Bigramm oder trigram Tabelle berechnen jeder gute Größe Korpus von englischem Text. Kurbel nur durch jedes Wort als Zeichen und Tally jeden Bigramm-Sie könnten dies als Hash-Griff mit einem bestimmten Bigramm als Schlüssel und ein inkrementierten ganzzahligen Zähler als Wert.

Englisch Morphologie und Englisch Phonetik ist (berühmt!) Weniger als isometrisches, so dass diese Technik könnte auch Strings erzeugen, die englischen „aussehen“, aber gegenwärtig mühsam prounciations. Dies ist ein weiteres Argument für trigrams eher als Bigramme-die Seltsamkeit durch Analyse der Klänge erzeugt, die mehrere Buchstaben in der Reihenfolge verwenden, um ein gegebenes Phonem zu erzeugen, wenn das den ganzen Sound erstreckt sie über n-Gramm reduziert werden. (Think "Pflug" oder "Tsunami", zum Beispiel.)

Es ist ganz einfach Englisch klingen Worte mit einer Markov-Kette zu erzeugen. Going nach hinten eine größere Herausforderung, aber. Was ist die akzeptable Marge für die Ergebnisse der Fehler? Man konnte immer eine Liste mit gemeinsamen Buchstabenpaare haben, Dreier-, etc, und Grade sie auf dieser Grundlage.

Sie sollten „aussprechbar“ Passwort-Generatoren erforschen, da sie die gleiche Aufgabe zu erfüllen versuchen.

Eine Perl-Lösung wäre Crypt :: PassGen , die Sie mit einem Wörterbuch trainieren können (so könnte man es auf verschiedene Sprachen trainieren, wenn Sie benötigen). Es geht durch das Wörterbuch und sammelt Statistiken über 1, 2, und 3-Buchstaben-Sequenzen, dann neue „Wörter“ baut basierend auf relativen Häufigkeiten.

Metaphone und Double Metaphone SOUNDEX ähnlich sind, außer daß sie mehr auf Ihr Ziel abgestimmt werden kann, als SOUNDEX . Sie sind entworfen Worte „hash“ auf der Grundlage ihrer Laut „Sound“, und sind gut auf diese für die englische Sprache zu tun (aber nicht so viel anderen Sprachen und Eigennamen).

Eine Sache, mit allen drei Algorithmen im Auge zu behalten ist, dass sie extrem empfindlich auf den Anfangsbuchstaben Ihres Wortes sind. Zum Beispiel, wenn Sie versuchen, wenn KEAL , um herauszufinden, ist Englisch klingender, werden Sie nicht ein Spiel zu REAL , da die Anfangsbuchstaben sind anders finden.

Ich würde versucht sein, den Algorithmus soundex über ein Wörterbuch der englischen Wörter zu laufen und die Ergebnisse zwischenzuspeichern, dann Kandidatenkette und Match gegen den Cache soundex.

Je nach Leistungsanforderungen, Sie könnten einen Abstand Algorithmus für soundex Codes arbeiten und akzeptieren Strings innerhalb einer gewissen Toleranz.

Soundex ist sehr einfach zu implementieren - siehe Wikipedia für eine Beschreibung der Algorithmus.

Eine beispielhafte Implementierung von dem, was Sie tun wäre, mögen: 

def soundex(name, len=4):
    digits = '01230120022455012623010202'
    sndx = ''
    fc = ''

    for c in name.upper():
        if c.isalpha():
            if not fc: fc = c
            d = digits[ord(c)-ord('A')]
            if not sndx or (d != sndx[-1]):
                sndx += d

    sndx = fc + sndx[1:]
    sndx = sndx.replace('0','')
    return (sndx + (len * '0'))[:len]

real_words = load_english_dictionary()
soundex_cache = [ soundex(word) for word in real_words ]

if soundex(candidate) in soundex_cache:
    print "keep"
else:
    print "discard"

Natürlich müssen Sie eine Implementierung von read_english_dictionary zur Verfügung zu stellen.

Bearbeiten : Ihr Beispiel von "KEAL" wird in Ordnung sein, da sie den gleichen soundex Code (K400) als "KIEL" hat. Sie müssen möglicherweise abgelehnt Wörter protokollieren und diese manuell überprüfen, ob Sie eine Vorstellung von Ausfallrate erhalten möchten.

Haben sie wirklich englische Wörter sein, oder einfach nur Zeichenfolgen, die sie aussehen englische Wörter sein könnte?

Wenn sie müssen nur aussehen wie möglich Englisch Worte, die Sie könnten einige statistische Analyse auf einigen echten englischen Texten tun und herausfinden, welche Kombinationen von Buchstaben häufig auftreten. Sobald Sie das getan haben, Sie Strings werfen können, die zu unwahrscheinlich sind, obwohl einige von ihnen echte Worte sein können.

Oder Sie könnten nur ein Wörterbuch verwenden und lehnen Wörter, die nicht in ihr sind (mit einigen Zulagen für Plurale und andere Variationen).

Sie könnten sie zu einem Wörterbuch vergleichen (frei im Internet verfügbar), aber das kann in Bezug auf die CPU-Auslastung teuer sein. Other than that, ich weiß nicht, irgendeinen anderen programmatischen Weg, es zu tun.

Das klingt ziemlich eine aufwendige Aufgabe! Aus der Spitze von meinem Kopf, ein Konsonanten Phonem braucht eine Vokal entweder vor oder nach ihm. Die Bestimmung, was ein Phonem allerdings wird ziemlich hart! Sie werden wahrscheinlich von ihnen manuell eine Liste schreiben müssen. Zum Beispiel: "TR" ist ok, aber nicht "TD", etc.

Ich würde wahrscheinlich jedes Wort mit einem SOUNDEX-Algorithmus mit einer Datenbank von Englisch Worten bewerten. Wenn Sie diese auf einem SQL-Server tun soll es ziemlich einfach sein, eine Datenbank einzurichten, eine Liste der meisten Worte Englisch (mit einem frei verfügbaren Wörterbuch) enthält, und MSSQL Server SOUNDEX implementiert als verfügbaren Such-Algorithmus.

Natürlich können Sie diese selbst implementieren, wenn Sie wollen, in jeder Sprache - aber es könnte eine schwierige Aufgabe sein.

So können Sie eine Auswertung erhalten würde, wie viel jedes Wort klingt wie ein bestehendes Wort Englisch, falls vorhanden, und man konnte Setup einige Grenzen für wie tief man sich wünschen Ergebnisse zu akzeptieren. Sie würden wahrscheinlich zu prüfen, wie die Ergebnisse für mehrere Wörter zu kombinieren, und Sie würden wahrscheinlich die Akzeptanz-Grenzen basieren auf dem Test zwicken.

Ich würde vorschlagen, bei dem phi-Test und Index der Übereinstimmung suchen. http://www.threaded.com/cryptography2.htm

Ich würde ein paar einfache Regeln vorschlagen und Standard-Paare und Drillinge wäre gut.

Zum Beispiel neigen Englisch klingende Worte dem Muster der Vokal-Konsonanten-Vokal zu folgen, abgesehen von einigen Diphthonge und Standard-Konsonanten Paaren (z th, dh und ei, oo, tr). Mit einem System wie, dass Sie Streifen sollten fast alle Worte, die nicht klingen wie sie Englisch sein könnte. Sie würden bei genauerem Hinsehen feststellen, dass Sie wahrscheinlich eine Menge Worte werden Streifen aus, die auch wie Englisch klingen, aber Sie können dann Regeln beginnen hinzufügen, die manuell für eine breitere Palette von Worten und ‚Zug‘ Ihr Algorithmus ermöglichen.

Sie werden nicht alle falsch-negative Ergebnisse entfernen (zB Ich glaube nicht, dass Sie mit einer Regel kommen verwalten können, ohne explizit Codierung in diesem Rythmus ‚Rythmus‘ enthalten ist ein Wort), aber es wird ein Verfahren zur Filterung zur Verfügung stellen .

Ich gehe davon aus, dass auch Sie Strings wollen, die Worte Englisch sein könnte (sie klingen vernünftig, wenn ausgesprochen) eher als Zeichenfolgen, die definitiv Wörter mit Englisch Bedeutung sind.

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