Аранжировка писем самым выразительным способом?

Question

У меня есть строка с некоторыми символами, и я ищу организацию этих символов, чтобы она была максимально возможной.

Например, если у меня есть буквы «ascrlyo», есть некоторые механизмы, которые были бы более произносимыми, чем другие. Следующее может получить "высокий балл":

scaroly crasoly

Где в дальнейшем может получить низкий балл:

oascrly yrlcsoa

Есть ли простой алгоритм, который я могу использовать? Или еще лучше, функциональность Python, которая достигает этого?

Спасибо!

Answer 1

Начните с решения более простой проблемы: является ли данное слово произносимым?

Может быть эффективным может быть обучение машинистов «контролируемое обучение». Обучайте бинарный классификатор на обучающем наборе словарных слов и скремблированных слов (предположим, что скремблированные слова являются непроизносимыми). Для функций я предлагаю считать битрамы и триграммы. Мое рассуждение: непроизносимые триграммы, такие как «tns» и «srh», редко встречаются в словарных словах, хотя отдельные буквы являются общими.

Идея состоит в том, что обученный алгоритм научится классифицировать слова с помощью любых редких триграмм как непроизносимых, а слова с только обычными триграммами, как произносимые.

---

Вот реализация с scikit-узнать точность 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 вскарабкался слова, которые он классифицирует произносимых:

• моро garapm ocenfir onerixoatteme arckinbo raetomoporyo bheral accrene cchmanie suroatipsheq

И, наконец, 10 слов из словаря неправильно классифицирован, как unpronouncable:

• ilch хаос Usnea halfpaced pyrostilpnite Lynnhaven жесток вступать в силу moldproof по частям

Answer 2

(Для полноты картины, вот мой оригинальный чистый 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%.