У меня есть строка с некоторыми символами, и я ищу организацию этих символов, чтобы она была максимально возможной.
Например, если у меня есть буквы "ascrlyo", есть некоторые меры, которые были бы более выраженными, чем другие. Следующие могут получить "высокий балл":
scaroly crasoly
Где ниже можно получить низкий балл:
oascrly yrlcsoa
Есть ли простой алгоритм, который я могу использовать? Или еще лучше, функциональность Python, которая достигает этого?
Спасибо!
Начнем с решения более простой задачи: является ли данное слово произносимым?
Механическое обучение "контролируемое обучение" может быть эффективным здесь. Обучайте бинарный классификатор на обучающем наборе словарных слов и скремблированных слов (предположим, что скремблированные слова являются непроизносимыми). Для функций я предлагаю считать битрамы и триграммы. Мое рассуждение: непроизносимые триграммы, такие как "tns" и "srh", редко встречаются в словарных словах, хотя отдельные буквы являются общими.
Идея состоит в том, что обученный алгоритм научится классифицировать слова с помощью любых редких триграмм как непроизносимых, а слова с только обычными триграммами, как произносимые.
Здесь реализация с scikit-learn http://scikit-learn.org/
import random
def scramble(s):
return "".join(random.sample(s, len(s)))
words = [w.strip() for w in open('/usr/share/dict/words') if w == w.lower()]
scrambled = [scramble(w) for w in words]
X = words+scrambled
y = ['word']*len(words) + ['unpronounceable']*len(scrambled)
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y)
from sklearn.pipeline import Pipeline
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.naive_bayes import MultinomialNB
text_clf = Pipeline([
('vect', CountVectorizer(analyzer='char', ngram_range=(1, 3))),
('clf', MultinomialNB())
])
text_clf = text_clf.fit(X_train, y_train)
predicted = text_clf.predict(X_test)
from sklearn import metrics
print(metrics.classification_report(y_test, predicted))
Он набирает точность 92%. В любом случае данная способность к восприятию субъективна, это может быть так же хорошо, как и получается.
precision recall f1-score support
scrambled 0.93 0.91 0.92 52409
word 0.92 0.93 0.93 52934
avg / total 0.92 0.92 0.92 105343
Это согласуется с вашими примерами:
>>> text_clf.predict("scaroly crasoly oascrly yrlcsoa".split())
['word', 'word', 'unpronounceable', 'unpronounceable']
Для любопытных здесь 10 скремблированных слов, которые он классифицирует:
И, наконец, 10 словарных слов, неправильно классифицированных как unpronouncable:
(Для полноты, здесь мое первоначальное чистое решение Python, которое вдохновило меня на то, чтобы попробовать машинное обучение.)
Я согласен, что надежное решение потребует сложной модели английского языка, но, возможно, мы сможем придумать простую эвристику, которая будет терпимо плохой.
Я могу думать о двух основных правилах, выполняемых большинством произносимых слов:
1. contain a vowel sound
2. no more than two consonant sounds in succession
В качестве регулярного выражения это можно записать c?c?(v+cc?)*v*
Теперь упрощенная попытка идентифицировать звуки из орфографии:
vowels = "a e i o u y".split()
consonants = "b bl br c ch cr chr cl ck d dr f fl g gl gr h j k l ll m n p ph pl pr q r s sc sch sh sl sp st t th thr tr v w wr x y z".split()
Тогда это возможно для правил с регулярными выражениями:
v = "({0})".format("|".join(vowels))
c = "({0})".format("|".join(consonants))
import re
pattern = re.compile("^{1}?{1}?({0}+{1}{1}?)*{0}*$".format(v, c))
def test(w):
return re.search(pattern, w)
def predict(words):
return ["word" if test(w) else "scrambled" for w in words]
Это составляет около 74% от набора слов/скремблированных тестов.
precision recall f1-score support
scrambled 0.90 0.57 0.70 52403
word 0.69 0.93 0.79 52940
avg / total 0.79 0.75 0.74 105343
Измененная версия набрала 80%.