有没有更有效的方法来使用 grep 进行拼字游戏搜索？

Question

我在 unix 中解决以下问题

假设您正在玩拼字游戏。你的架子上有以下七个字母——E A F N A S M。这些是你可以用来组成单词的字母，你可以在你的单词中使用任意数量的字母，但必须至少使用一个。您正在尝试将一个词放在板上已经有一个词的地方：ARE。

您的目标是找到一个词，该词将与您机架中的字母一起附加到 ARE 一词上。虽然通常您的字母可能会放在 ARE 之前或之后以构成新单词，但在这种情况下，ARE 位于棋盘的边缘，因此您的单词必须以 ARE 结尾。您的目标是使用 grep.
在 /usr/dict/words 中找到所有符合这些条件的可能单词

我想出的命令确实效率低下但有效。

grep “^[eafnasm][eafnasm]*are$” /usr/dict/words |
grep -v “a.*a.*a.*a” |
grep -v “e.*e.*e” |
grep -v “f.*f” |
grep -v “n.*n” |
grep -v “s.*s” |
grep -v “m.*m” |
grep -v “^...........”

有没有更有效的方法？

Answer 1

一种加快速度的方法是：

grep -E '^[aefmns]{1,7}are$' /usr/dict/words |
grep -Ev 'a.*a.*a.*a|e.*e.*e|f.*f|n.*n|s.*s|m.*m'

它减少了查看数据的进程数。我从初始字符 class 中删除了第二个 A，因为它是多余的，但重复代表的成本可以忽略不计。在第一个模式中使用 {1,7} 限定符意味着无需在第二个模式中过滤超长名称。

请注意，第一次搜索不允许多个 R 通过。这是手写字母和板载文字的特定组合的专业化。如果手拿着一个 R（而不是说，第二个 A），那么有必要从结果中过滤出超过 2 个 R（两个因为在这种情况下，手上有一个 R，单词中有一个在电路板上），并且多 A 滤波器也必须改变。

请注意，此处的更改只是对原来的 8 个 grep 命令运行的微小调整。由于解决方案需要使用 grep（排除 Perl、Python、Awk、...），您可能无法使用少于两个命令，一个 'positive' grep 到 select 种可能性，以及一种 'negative' grep 来消除不可能。使用自定义工具（用 C 或 C++ 或类似语言编写的专用程序），您可能会做得更好。

如果您的 grep 版本支持 PCRE（与 Perl 兼容的正则表达式），您也许可以做到 'all in one'。我相当确定它的可读性和可理解性会降低，并且虽然它的性能可能会好一些（I/O 更少，因为没有管道），但必须衡量性能改进。有时候，越简单越好。

有没有更有效的方法来使用 grep 进行拼字游戏搜索？

Is there a more efficient way to do scrabble search with grep?

regex

unix

grep

command

words