如何使用Perl從一組字母中生成單詞列表？

Question

我正在尋找一個模塊，正則表達式或其他可能適用於這個問題的東西。

如何以編程方式解析字符串並創建已知的英文& |西班牙文的詞，因爲我有一個字典表，我可以檢查算法隨機匹配的每個排列？

給定一組字符：EBLAIDL KDIOIDSI ADHFWB

程序應返回：BLADEAIDKIDKIDSFIDDLEHOLA等....

我也希望能夠定義最小&最大字長以及音節數

輸入長度無關緊要，它必須只有字母，而且標點符號無所謂。

感謝所有幫助

編輯
字母輸入字符串可以重複使用。

例如，如果輸入的是：ABLED則輸出可能包含：BALL或BLEED

Answer 1

好了，正則表達式是相當容易的......然後你只需要通過在字典中的單詞進行迭代。 EG，假設一個標準的linux：

# perl -n -e 'print if (/^[EBLAIDL]+$/);' /usr/share/dict/words 

將快速返回該文件中包含這些和那些字母的所有單詞。

A 
AA 
AAA 
AAAA 
AAAAAA 
AAAL 
AAE 
AAEE 
AAII 
AB 
... 

正如你所看到的，你需要一個值得 擁有的字典文件。特別是，我的Fedora系統 上的/ usr/share/dict/words包含一堆帶有所有As的單詞，這些單詞可能是或可能不是 。所以請仔細選擇你的字典文件。

對於min的最大長度，你可以很快發現，還有：

$min = 9999; 
$max = -1; 
while(<>) { 
    if (/[EBLAIDL]+$/) { 
     print; 
    chomp; 
     if (length($_) > $max) { 
    $max = length($_); 
    $maxword = $_; 
     } 
     if (length($_) < $min) { 
    $min = length($_); 
    $minword = $_; 
     } 
    } 
} 

print "longest: $maxword\n"; 
print "shortest: $minword\n"; 

會產生：

ZI 
ZMRI 
ZWEI 
longest: TANSTAAFL 
shortest: A 

對於破字成塊和計數音節是非常特定於語言的，因爲已在上述評論中提及。

Answer 2

您還沒有指定，所以我假設輸入中的每個字母只能使用一次。

[你有因爲在輸入指定的字母可以多次使用，但我要萬一有人在這裏離開這個崗位發現它是有用的。]

以這樣高效是關鍵對單詞中的字母進行排序。

abracadabra => AAAAABBCDRR 
abroad  => AABDOR 
drab  => ABDR 

然後很明顯，「單調」是在「abracadabra」。這個「國外」不是。

abracadabra => AAAAABBCD RR 
abroad  => AA B DOR 

讓我們調用排序後的字母「簽名」。如果您可以從「A」的簽名中刪除字母以獲得「B」的簽名，則單詞「B」在單詞「A」中。這很容易檢查使用正則表達式模式。

sig('drab') =~ /^A?A?A?A?A?B?B?C?D?R?R?\z/ 

或者，如果，如果我們消除了不必要的效率回溯，我們可以得到

sig('drab') =~ /^A?+A?+A?+A?+A?+B?+B?+C?+D?+R?+R?+\z/ 

現在我們知道我們想要的模式，它只是一個構建它的問題。

use strict; 
use warnings; 
use feature qw(say); 

sub sig { join '', sort grep /^\pL\z/, split //, uc $_[0] } 

my $key = shift(@ARGV); 

my $pat = sig($key); 
$pat =~ s/.\K/?+/sg; 
my $re = qr/^(?:$pat)\z/s; 

my $shortest = 9**9**9; 
my $longest = 0; 
my $count = 0; 
while (my $word = <>) { 
    chomp($word); 
    next if !length($word); # My dictionary starts with a blank line!! 
    next if sig($word) !~ /$re/; 
    say $word; 
    ++$count; 
    $shortest = length($word) if length($word) < $shortest; 
    $longest = length($word) if length($word) > $longest; 
} 

say "Words: $count"; 
if ($count) { 
    say "Shortest: $shortest"; 
    say "Longest: $longest"; 
} 

例子：

$ perl script.pl EBLAIDL /usr/share/dict/words 
A 
Abe 
Abel 
Al 
... 
libel 
lid 
lie 
lied 

Words: 117 
Shortest: 1 
Longest: 6 

Answer 3

我能想象這會工作會在字母所有可能的組合來分析，並將它們與對字典的唯一途徑。將它們與字典進行比較的最快方法是將該字典轉換爲散列。這樣，你可以快速查找這個單詞是否是一個有效的單詞。

我用詞典中的所有字母鍵入我的詞典，然後刪除任何非alpha字符以保證安全。對於這個值，我會存儲實際的字典單詞。例如：

cant => "can't", 
google => "Google", 

這樣，我就可以顯示拼寫正確的單詞。

我發現Math::Combinatorics看起來不錯，但沒有按照我希望的方式工作。你給它一個字母列表，它會返回你指定的字母數的所有組合。因此，我認爲我所要做的就是將這些字母轉換爲單個字母的列表，並簡單地遍歷所有可能的組合！

不......這給了我所有的無序組合。然後，我必須對每個組合列出所有可能的字母排列。胡說！ Ptooy！ Yech！

因此，循環中臭名昭着的循環。其實，三個循環。 *外層循環只需將所有數字的組合從1到單詞中的字母數倒計數。 *下一個查找每個字母組的所有無序組合。 *最後，最後一個採用所有無序組合並從這些組合中返回一個排列列表。

現在，我終於可以把這些字母組合與我的字典進行比較。令人驚訝的是，程序的運行速度比我預想的要快得多，因爲考慮到它必須將235,886字的字典變成散列，然後循環通過三層循環來查找所有可能數量字母的所有組合的所有排列。整個程序在不到兩秒的時間內運行。

#! /usr/bin/env perl 
# 
use strict; 
use warnings; 
use feature qw(say); 
use autodie; 
use Data::Dumper; 

use Math::Combinatorics; 

use constant { 
    LETTERS => "EBLAIDL", 
    DICTIONARY => "/usr/share/dict/words", 
}; 

# 
# Create Dictionary Hash 
# 

open my $dict_fh, "<", DICTIONARY; 
my %dictionary; 
foreach my $word (<$dict_fh>) { 
    chomp $word; 
    (my $key = $word) =~ s/[^[:alpha:]]//; 
    $dictionary{lc $key} = $word; 
} 

# 
# Now take the letters and create a Perl list of them. 
# 

my @letter_list = split // => LETTERS; 
my %valid_word_hash; 

# 
# Outer Loop: This is a range from one letter combinations to the 
# maximum letters combination 
# 
foreach my $num_of_letters (1..scalar @letter_list) { 

    # 
    # Now we generate a reference to a list of lists of all letter 
    # combinations of $num_of_letters long. From there, we need to 
    # take the Permutations of all those letters. 
    # 
    foreach my $letter_list_ref (combine($num_of_letters, @letter_list)) { 
     my @letter_list = @{$letter_list_ref}; 

     # For each combination of letters $num_of_letters long, 
     # we now generate a permeation of all of those letter 
     # combinations. 
     # 
     foreach my $word_letters_ref (permute(@letter_list)) { 
      my $word = join "" => @{$word_letters_ref}; 

      # 
      # This $word is just a possible candidate for a word. 
      # We now have to compare it to the words in the dictionary 
      # to verify it's a word 
      # 
      $word = lc $word; 
      if (exists $dictionary{$word}) { 
       my $dictionary_word = $dictionary{$word}; 
       $valid_word_hash{$word} = $dictionary_word; 
      } 
     } 
    } 
} 

# 
# I got lazy here... Just dumping out the list of actual words. 
# You need to go through this list to find your longest and 
# shortest words. Number of syllables? That's trickier, you could 
# see if you can divide on CVC and CVVC divides where C = consonant 
# and V = vowel. 
# 
say join "\n", sort keys %valid_word_hash; 

運行這個程序產生：

$ ./test.pl | column 
a   al    balei   bile   del   i    lai 
ab   alb   bali   bill   delia   iba   laid 
abdiel  albe   ball   billa   dell   ibad   lea 
abe  albi   balled   billed   della   id    lead 
abed  ale   balli   blad   di    ida   leal 
abel  alible   be    blade   dial   ide   led 
abide  all   bea   blae   dib   idea   leda 
abie  alle   bead   d    die   ideal   lei 
able  allie   beal   da    dieb   idle   leila 
ad   allied   bed   dab   dill   ie    lelia 
ade  b    beid   dae   e    ila   li 
adib  ba    bel   dail   ea    ill   liable 
adiel  bad   bela   dal   ed    l    libel 
ae   bade   beld   dale   el    la    lid 
ai   bae   belial   dali   elb   lab   lida 
aid  bail   bell   dalle   eld   label   lide 
aide  bal   bella   de    eli   labile   lie 
aiel  bald   bid   deal   elia   lad   lied 
ail  baldie   bide   deb   ell   lade   lila 
aile  bale   bield   debi   ella   ladle   lile 

Answer 4

也許你可以創建一個單獨的表，字母表中的26個字母，這將有助於。除此之外，您可以構建一個查詢，在第二個數據庫中搜索您定義的任何字母。查詢確保每個結果都是唯一的，這一點很重要。

所以，你有一個包含你的單詞的表，並且你有一個多對多的關係到另一個包含字母表的所有字母的表。你會在第二張桌子上查詢，並使結果獨一無二。你可以用類似的方法來處理這些字母的數量。

您可以對字母和音節的數量使用相同的方法。所以你會做一個查詢來加入你想要的所有信息。在數據庫中放置正確的索引以幫助提高性能，利用適當的緩存，如果涉及到這一點，則可以並行搜索。