3

類似した文字列 (単語) をマージしたい (文字列が他の文字列内にある)。 

 word
 wor 
 words
 wormhole
 hole

なるだろう：

words
wormhole

とwor重複する場合: word, words, wormhole-worは破棄されます。-
word破棄されます。-破棄されます。 しかし、オーバーラップしないでください。 これどうやってするの？ wordsword
holewormholehole
wordswormhole

編集
私の解決策は次のとおりです。 

while read a
do  
   grep $a FILE | 
   awk 'length > m { m = length; a = $0 } END { print a }'
done < FILE | 
sort -u

しかし、大規模なデータセットで問題が発生しないかどうかはわかりません。

4

10 に答える 10

3

ルビーの場合:

list = %w[word wor words wormhole]

list.uniq
.tap{|a| a.reverse_each{|e| a.delete(e) if (a - [e]).any?{|x| x.include?(e)}}}
于 2013-06-09T19:34:55.237 に答える
3

単語のリストが十分に長い場合、単語に対するネストされたループは非常に遅くなります。これは私がそれを行う方法です：

use strict;
use warnings;

use File::Slurp 'read_file';
chomp( my @words = read_file('/usr/share/dict/words') );

my %overlapped;
for my $word (@words) {
    $word =~ /(.*)(?{++$overlapped{$1}})(*FAIL)/;
    --$overlapped{$word};
}

print "$_\n" for grep ! $overlapped{$_}, @words;

単語を最長から最短に処理するという Darshan Computing の提案により、おそらく改善される可能性があります。

于 2013-06-09T20:20:47.553 に答える
2

ハッシュを使用して、単語リストの部分文字列を数えることができます。

use strict;
use warnings;
use feature 'say';

my %seen;                   # seen substrings
my @words;                  # original list
while (<DATA>) {            # read a new substring
    chomp;
    push @words, $_;        # store the original
    while (length) {        # while a substring remains
            $seen{$_}++;    # increase its counter
            chop;           # shorten the substring
    }
}

# All original words with count == 1 are the merged list
my @merged = grep $seen{$_} == 1, @words;

say for @merged;

__DATA__
w
word
wor
words
wormhole
hole
holes

出力：

words
wormhole
holes

もちろん、ハッシュ キーは正確であり、キーは keyFooとは異なるため、大文字と小文字、句読点、および空白を補正する必要がありますfoo。

于 2013-06-09T20:14:32.853 に答える
1

any/でリスト内包表記を使用しますall。

>>> lis = ['word','wor', 'words', 'wormhole']
#all
>>> [x for x in lis if all(x not in y for y in lis if y != x)]
['words', 'wormhole']
#any
>>> [x for x in lis if not any(x in y for y in lis if y != x)]
['words', 'wormhole']

ここでもmarisa_trieを使用できます。

>>> import marisa_trie
>>> lis = ['word','wor', 'words', 'wormhole', 'hole', 'holes']
>>> def trie(lis):
        trie = marisa_trie.Trie(lis)
        return [x for x in lis if len(trie.keys(unicode(x))) ==1 ]
... 
>>> trie(lis)
['words', 'wormhole', 'holes']
于 2013-06-09T19:01:16.277 に答える
1

長い perl ワンライナー、

perl -nE 'chomp;($l,$p)=($_,0); @w=grep{ $p=1 if /$l/; $p|| $l!~/$_/} @w; $p or push @w,$l}{say for @w' file
于 2013-06-09T22:36:41.127 に答える
1

アモンの提案は...

すべての単語のリストを昇順に並べ替えます。単語が次の単語の部分文字列である場合、現在の単語を破棄します。それ以外の場合は先に進みます。

...ソートにはO(n log n)が必要です.Ashwiniのソリューションの時間の複雑さについてはわかりませんが、O(n log n)以上のようです.

これはO（n）ソリューションだと思います...

from collections import defaultdict

words = ['word', 'wor', 'words', 'wormhole']

infinite_defaultdict = lambda: defaultdict(infinite_defaultdict)

mydict = infinite_defaultdict()
for word in words:
    d = mydict
    for char in word:
        d = d[char]

result = []
for word in words:
    d = mydict
    for char in word:
        d = d[char]
    if not d:
        result.append(word)

print result

...印刷...

['words', 'wormhole']

アップデート

しかし、大規模なデータセットで問題が発生しないかどうかはわかりません。

比較のために、 から 10,000 語を使用すると/usr/share/dict/words、これには約 70 ミリ秒の CPU 時間がかかりますが、Ashwini の場合は約 11 秒かかります。

更新 2

わかった。元の質問は、単語が最初にのみ重複できるかのように読みましたが、どこでも重複できる場合、このコードは機能しません。それを行うことができるアルゴリズムは、最悪の場合の複雑さが O(n²) になると思います。

于 2013-06-09T19:20:49.987 に答える
1

bash ソリューション:

#!/bin/bash
dict="word wor words wormhole hole "
uniq=()

sort_by_length() {
    for word; do
        printf "%d %s\n" ${#word} "$word"
    done | sort -n | cut -d " " -f2-
}
set -- $(sort_by_length $dict)

while [[ $# -gt 0 ]]; do
    word=$1
    shift
    found=false
    for w;  do
        if [[ $w == *"$word"* ]]; then
            found=true
            break
        fi
    done
    if ! $found; then
        uniq+=($word)
    fi
done

echo "${uniq[@]}"
于 2013-06-09T21:22:51.363 に答える