使用grep从根目录已经存在的字典中删除单词

我正在尝试写一个随机密码生成器。 我有一个单词字典,我想删除词根已经在字典中的单词,以便一个字典,看起来像:

ablaze able abler ablest abloom ably 

最终只会结束

 ablaze able abloom ably 

因为能和能够包含以前使用的能力。

我宁愿用grep来做这件事,这样我就可以更多地了解它的工作原理。 我有能力写一个程序在C或Python将做到这一点。

Solutions Collecting From Web of "使用grep从根目录已经存在的字典中删除单词"

如果对列表进行排序,以使较短的字符串总是在较长的字符串之前,那么可以通过简单的Awk脚本获得相当好的性能。

 awk '$1~r && p in k { next } { k[$1]++; print; r= "^" $1; p=$1 }' words 

如果当前单词匹配前缀正则表达式r (在某个时刻定义)并且前缀p (同上)在可见键列表中,则跳过。 否则,将当前单词添加到前缀键中,打印当前行,创建一个匹配当前行的正则表达式(现在是前缀正则表达式r ),还记住p的前缀字符串。

如果所有类似的字符串总是相邻的(就像你在词法上对文件进行排序一样),我猜也可以完全消除kp

 awk 'NR>1 && $1~r { next } { print; r="^" $1 }' words 

这是基于输入文件被排序的假设。 在这种情况下,当查找每个单词时,第一个单词之后的所有匹配都可以安全地跳过(因为它们将对应于“具有不同后缀的相同单词”)。

 #/bin/bash input=$1 while read -r word ; do # ignore short words if [ ${#word} -lt 4 ] ; then continue; fi # output this line echo $word # skip next lines that start with $word as prefix skip=$(grep -c -E -e "^${word}" $input) for ((i=1; i<$skip; i++)) ; do read -r word ; done done <$input 

调用./filter.sh input > output

对于在我的/usr/share/dict/american-english词典中找到的4个或更多字母的所有单词,这需要少于2分钟的时间。 算法是O(n²),因此不适合大文件。

但是,如果您完全避免使用grep,则可以加快速度。 这个版本只需要4秒钟的时间来完成这项工作(因为它不需要每个单词扫描整个文件几乎一次)。 由于它在输入上执行一次传递,因此其复杂度为O(n):

 #/bin/bash input=$1 while true ; do # use already-read word, or fail if cannot read new if [ -n "$next" ] ; then word=$next; unset next; elif ! read -r word ; then break; fi # ignore short words if [ ${#word} -lt 4 ] ; then continue; fi # output this word echo ${word} # skip words that start with $word as prefix while read -r next ; do unique=${next#$word} if [ ${#next} -eq ${#unique} ] ; then break; fi done done <$input 

假设你想从共享前四(最多十个)字母的单词开始,你可以这样做:

 cp /usr/share/dict/words words str="...." for num in 4 5 6 7 8 9 10; do for word in `grep "^$str$" words`; do grep -v "^$word." words > words.tmp mv words.tmp words done str=".$str" done 

你不想从一个字母开始,除非字典中没有“a”等。

试试这个BASH脚本:

 a=() while read -rw; do [[ ${#a[@]} -eq 0 ]] && a+=("$w") && continue grep -qvf <(printf "^%s\n" "${a[@]}") <<< "$w" && a+=("$w") done < file printf "%s\n" "${a[@]}" ablaze able abloom ably 

好像你想把副词组合在一起。 一些副词,包括那些也可以是形容词的副词,用呃和est来形成比较:

  • 能干,能干,能干
  • 更快,更快,最快
  • 很快,最快,最快
  • 容易,容易,最简单

这个过程在自然语言处理中是知道的,并且可以使用stemmer或lemmatizer来实现。 python的NLTK模块中有很多流行的实现,但问题还没有完全解决。 盒子干的最好的东西是雪球stemmer,但它不会干扰副词的根源。

 import nltk initial = ''' ablaze able abler ablest abloom ably fast faster fastest '''.splitlines() snowball = nltk.stem.snowball.SnowballStemmer("english") stemmed = [snowball.stem(word) for word in initial] print set(stemmed) 

输出…

 set(['', u'abli', u'faster', u'abl', u'fast', u'abler', u'abloom', u'ablest', u'fastest', u'ablaz']) 

另一个选择是使用正则表达式,但这恐怕有其自己的困难。

 patterns = "er$|est$" regex_stemmer = nltk.stem.RegexpStemmer(patterns, 4) stemmed = [regex_stemmer.stem(word) for word in initial] print set(stemmed) 

输出…

 set(['', 'abloom', 'able', 'abl', 'fast', 'ably', 'ablaze']) 

如果你只是想删除一些单词,这个总的命令将起作用。 请注意,它会抛出一些合法的词最好,但它是简单的死。 它假定你有一个test.txt文件,每行一个字

egrep -v "er$|est$" test.txt >> results.txt

egrep与grep -E相同。 -v表示丢出匹配的行。 x|y表示如果x y匹配,并且$表示行尾,那么您会查找以er或est结尾的单词