Генерация разумных строк, используя шаблон - PullRequest
Новая
       9

Генерация разумных строк, используя шаблон

0 голосов
/ 26 июля 2011

У меня есть таблица строк (около 100 000) в следующем формате: 

pattern , string

например. - 

*l*ph*nt , elephant
c*mp*t*r , computer
s*v* , save
s*nn] , sunny
]*rr] , worry

Для упрощения предположим, что * обозначает гласный, согласный остается неизменным, а ] обозначает либо y, либо w (скажем, например, полу-гласные / круглые гласные в фонологии) .

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

например. -

h * ll * -> Привет, привет, привет ...

«Алло» разумно, потому что «ха», «ал», «ло» можно увидеть в наборе данных, как со словами «иметь», «также», «низкий». Две буквы 'll' не учитываются, поскольку они были указаны в шаблоне.

Каковы простые и эффективные способы сделать это? Существуют ли какие-либо библиотеки / структуры для достижения этой цели?

У меня нет определенного языка, но я предпочитаю использовать Java для этой программы.

Ответы [ 2 ]

0 голосов
/ 27 июля 2011

Это особенно хорошо подходит для Python itertools , set и re операций: 

import re
import itertools

VOWELS      = 'aeiou'
SEMI_VOWELS = 'wy'
DATASET     = '/usr/share/dict/words'
SENSIBLES   = set()

def digraphs(word, digraph=r'..'):
    '''
    >>> digraphs('bar')
    set(['ar', 'ba'])
    '''
    base = re.findall(digraph, word)
    base.extend(re.findall(digraph, word[1:]))
    return set(base)

def expand(pattern, wildcard, elements):
    '''
    >>> expand('h?', '?', 'aeiou')
    ['ha', 'he', 'hi', 'ho', 'hu']
    '''
    tokens = re.split(re.escape(wildcard), pattern)
    results = set()
    for perm in itertools.permutations(elements, len(tokens)):
        results.add(''.join([l for p in zip(tokens, perm) for l in p][:-1]))
    return sorted(results)

def enum(pattern):
    not_sensible = digraphs(pattern, r'[^*\]]{2}')
    for p in expand(pattern, '*', VOWELS):
        for q in expand(p, ']', SEMI_VOWELS):
            if (digraphs(q) - not_sensible).issubset(SENSIBLES):
                print q

## Init the data-set (may be long...)
## you may want to pre-compute this
## and adapt it to your data-set.
for word in open(DATASET, 'r').readlines():
    for digraph in digraphs(word.rstrip()):
        SENSIBLES.add(digraph)

enum('*l*ph*nt')
enum('s*nn]')
enum('h*ll*')
0 голосов
/ 26 июля 2011

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

ee    1024 times
su    567 times
...
xy    45 times
xz    0 times

Таблица будет небольшой, поскольку у вас будет только около 26 * 26 = 676 значений для хранения.

Вы должны сделать это только один раз для своего набора данных (или обновлять таблицу каждый раз, когда она изменяется, если набор данных является динамическим) и можете использовать таблицу для оценки возможных строк. Например, для вашего примера добавьте значения для «ha», «al» и «lo», чтобы получить «оценку» для строки «hallo». После этого выберите строку (ы) с наибольшим количеством баллов.

Обратите внимание, что оценка может быть улучшена путем проверки более длинных подстрок, например три буквы, но это также приведет к большим таблицам.

...