脚本查找单词列表中给定单词内的单词

Question

我有一个包含250K单词（txt文件）的字典。对于每一个词，我想提出一个脚本，它会抛出所有可能的字谜（每个字谜也应该在字典中）。

理想的脚本将这种格式输出：

字1：anagram1，anagram2 ...

单词2：anagram1，anagram2 ...

任何帮助将是很大的赞赏。

Answer 1

我Perl到目前为止已经试过什么：

use strict; 
use warnings; 

use Algorithm::Combinatorics qw(permutations); 

die "First argument should be a dict\n" unless $ARGV[0] or die $!; 
open my $fh, "<", $ARGV[0] or die $!; 

my @arr = <$fh>; 
my $h = {}; 

map { chomp; $h->{lc($_)} = [] } @arr; 

foreach my $word (@arr) { 
    $word = lc($word); 
    my $chars = [ ($word =~ m/./g) ]; 
    my $it = permutations($chars); 

    while (my $p = $it->next) { 
     my $str = join "", @$p; 

     if ($str ne $word && exists $h->{$str}) { 
      push @{ $h->{$word} }, $str 
       unless grep { /^$str$/ } @{ $h->{$word} }; 
     } 
    } 

    if (@{ $h->{$word} }) { 
     print "$word\n"; 
     print "\t$_\n" for @{ $h->{$word} }; 
    } 
} 

END{ close $fh; } 

有可能对速度的一些可能的改进，但它的作品。

我使用French dict来自wordsarchlinux包。

例

$ perl annagrammes.pl /usr/share/dict/french 
abaissent 
     absentais 
     abstenais 
abaisser 
     baissera 
     baserais 
     rabaisse 
(...) 

注意 要installl perl的模块：

cpan -i Algorithm::Combinatorics 

Answer 2

它必须是anagram星期。

我打算将您提交给我提交给前一个问题的答案：https://stackoverflow.com/a/12811405/128421。它显示了如何构建散列以快速搜索具有常见字母的单词。

为了您的目的，找到子字符串/内部词，您还需要找到可能的内部词。以下是如何快速定位的不同大小的字母独特组合的基础上，启动Word：

word = 'misses' 
word_letters = word.downcase.split('').sort 
3.upto(word.length) { |i| puts word_letters.combination(i).map(&:join).uniq } 

eim 
eis 
ems 
ess 
ims 
iss 
mss 
sss 
eims 
eiss 
emss 
esss 
imss 
isss 
msss 
eimss 
eisss 
emsss 
imsss 
eimsss 

一旦你有了这些组合，拆分它们（或不做join），并做一下起坐在哈希我以前的答案建立。

Answer 3

受this的启发，我建议你创建一个Trie。

然后，具有N个级别的trie将具有所有可能的anagrams（其中N是原始单词的长度）。现在，为了获得不同大小的单词，我建议你简单地遍历trie，即。对于所有3个字母的子字词，只需制作深度为3级的所有字符串即可。

我不太确定这一点，因为我没有测试这个，但这是一个有趣的挑战，而这个建议将是我将如何开始解决它。

希望它可以帮助一点点=）

Answer 4

h = Hash.new{[]} 
array_of_words.each{|w| h[w.downcase.chars.sort].push(w)} 
h.values