在以下格式使用圖案

我有字符串（約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的這個程序。

來源

2011-07-26 Olenayuko

這是特別適合的Python itertools，設置和重新操作：

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*')

來源

2011-07-26 21:46:20 fra

你應該早一點提到字母大小，然而這個解決方案會縮放。爲了記錄，它在1.6ms內產生60'\ * l \ * ph \ * nt'，在0.5ms內產生20'h \ * ll \ *'（在字典中有98569個字）。 – fra

可愛的解決方案。花了一些時間去理解它（我對Python相對來說比較陌生）。這是我一直在尋找的東西。謝謝@fra。 – Olenayuko

由於不會有太多的possibilites兩個字母串，你可以通過你的數據集，並生成包含每兩個字母串計數表，因此該表將是這個樣子：

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

表格會很小，因爲您只能存儲大約26 * 26 = 676個值。

您必須爲您的數據集只做一次這種操作（或者如果數據集是動態的，每次更改時都會更新表），並且可以使用該表評估可能的字符串。例如，爲你的例子，添加'ha'，'al'和'lo'的值以得到字符串'hallo'的「分數」。之後，選擇分數最高的字符串。

請注意，可以通過檢查更長的子字符串f.e來改進評分。三個字母，但這也會導致更大的表格。

來源

2011-07-26 11:26:29 schnaader

謝謝schnaader。 – Olenayuko

謝謝schnaader。我在這個問題上的字母不是英文，而是一個更大的字母。例如，它也包含重音字母。（比如à，á，â，ã，ä，ā，ă，± - 更像是一個擴展的拉丁字母 - 我正在使用Unicode）。我的目標是性能優化和內存使用最少。無論如何，我會嘗試看看子串表格得到的效果如何。 – Olenayuko

在以下格式使用圖案

回答

相關問題