☰

特定の順序に従う単語を見つける方法

tag-icon • tag-icon bash shell-script scripting
特定の順序に従う単語を見つける方法

文字の羅列が与えられたときに、可能性のあるすべての単語を検索するスクリプト (script1.sh) を作成しようとしています。

  • 単語は、文字の組み合わせの最初の文字で始まり、最後の文字で終わる必要があります。

  • 単語の文字は、ごちゃ混ぜになった文字の順序に従う必要があります。

  • 組み合わせた文字はそれぞれ複数回使用できます。

したがって、この

./script1.sh "qwertyuytresdftyuiokn"

queenandは出力されるはずquestionですが、"quieten" は出力されません。これは、"e" が "u" と "i" の前にあるためです。

最初の文字、最後の文字、残りの文字を変数に割り当て、egrep を使用して単語を検索しようとしましたが、文字の順序を使用する方法が見つかりませんでした。そのため、この場合も無効な単語が返されます。

#!/bin/bash

first_letter=$(echo $@ | cut -c1)
last_letter=$(echo $@ |rev| cut -c1)
remaining_letters=$(echo $@ | cut -c2- | rev | cut -c2-)

grep -E "^$first_letter[$remaining_letters]*$last_letter$" /usr/share/dict/words

次に、そのごちゃ混ぜの単語を配列に変換しようとしましたが、やはり、ごちゃ混ぜの単語の中で順序に従った単語を見つける方法が見つかりませんでした。

答え1

#!/bin/sh
pttrn="^$(printf '%s' "$1" | sed -e 's/\(.\)/\1*/g' -e 's/\*/\\+/' -e 's/\*$/\\+/')"'$'
grep "$pttrn" /usr/share/dict/words

最初の引数から各文字の後に を挿入することでパターンが取得されます*。次に、最初の が*に変更され\+、最後の も に変更されます*。さらに、^と$が追加されます。サンプル入力では、次のパターンが生成されます。

^q\+w*e*r*t*y*u*y*t*r*e*s*d*f*t*y*u*i*o*k*n\+$

このパターンは の正しいパターンですgrep。qは先頭に少なくとも 1 回出現する必要があり、n末尾に少なくとも 1 回出現する必要があります。 中間の各文字は 0 回以上出現する場合があり、順序は維持されます。

.このスクリプトは愚かなものであることに注意してください。 、[などを入力する]と、仕様を超えた正規表現が返されます。 適切な入力を行うか、スクリプトを拡張して検証してください。

例:

$ ./script1.sh qwertyuytresdftyuiokn
queen
question
$ ./script1.sh te
tee
$ ./script1.sh superuser
seer
serer
spur
super
supper
surer
$

答え2

これにアプローチする方法は1つあります

まず、単語リストをフィルタリングして、文字の羅列と同じ文字で始まり、終わる単語だけを抽出します。たとえば、文字の羅列が位置パラメータとして渡された場合$1（最近のbashシェルを想定）、

grep -x "${1:0:1}.*${1:(-1):1}" /usr/share/dict/words

次に、これらの単語をそれぞれ正規表現に分解します。これを行う「良い」方法は思いつきませんが、GNU sedを使用すると、たとえば次のようにすることができます。

$ sed -E 's/(.)\1*/+.*\1/2g' <<< "queen"
q+.*u+.*e+.*n

次に、生成された各パターンに対して、この混乱をテストします。

すべてを一緒に入れて：

$ cat script1 
#!/bin/bash

wordlist=/usr/share/dict/words

while IFS= read -r word; do 
  grep -qEx "$(sed -E 's/(.)\1*/+.*\1/2g' <<< "$word")" <<< "$1" && printf '%s\n' "$word"
done < <(grep -x "${1:0:1}.*${1:(-1):1}" "$wordlist")

それから

$ ./script1 qwertyuytresdftyuiokn
queen
question

答え3

もう一つの例を次に示します ( で実行bash)。pythonコードは正規表現を生成し、それを に入力しますgrep。grep次に、この由緒あるユーティリティの出力を処理しlook、バイナリ検索を実行して、例の で/usr/share/dict/words始まるすべての単語を取得します。これにより、検索する単語セットが大幅に削減されます。qgrep

python3 -c 'import sys
arr = list(sys.argv[1])
print(*arr, sep="*")
' $1 | grep -x -f - <(look ${1:0:1})

あるいは、正規表現を避けるlook+ソリューションpython3

look q | ./finder.py "qwertyuytresdftyuiokn"

ここでfinder.py、次のようになります。

#!/usr/bin/env python3
import sys
from itertools import groupby

seek_word = sys.argv[1]
for word in sys.stdin:
    orig_word = word.strip()
    word = ''.join(k for k, g in groupby(orig_word)) 
    s_w = iter(seek_word)
    i_word = iter(word)
    if all(c in s_w for c in i_word) and not next(s_w, None):
        print(orig_word)

関連情報