存在する組み合わせを数えたい

Question

例えば下のような文字列がある場合
あいう
あうえ
い
うい
この4つの文字列のうち同じ文字の組み合わせをもつ文字列を数えたいです。
上の場合、たとえば「あ」と「う」があるのは「あいう」と「あうえ」に含むので２、
「い」は「あいう」「い」「うい」に含むので３と数えたいです。
結果は下の表になります。

パターン	数
(あ)	2
(い)	3
(う)	3
(え)	1
(あ,い)	1
(あ,う)	2
(あ,え)	1
(い,う)	2
(あ,い,う)	1
(あ,う,え)	1

列１は組み合わせで、列2はその組み合わせを含む文字列の数です。
文字の長さがまちまち（最長十文字以上）で、かつ実際は数十万の文字列かつ漢字があるので上記の例の「いえ」など存在しない組み合わせまではできれば数えないようにしたいです。
現在のところ皆目見当がついていない状況なので何か教えていただけましと幸いです。

環境
Python3.6

Comments

[KojiDoi]

「あ」は「あい」「あう」などにも含まれますが、こういうのは重複カウントするのですか？

[midsum0323]

1文字の場合、2文字の場合...と全ての場合を数えたいです。

[Zuishin]

「い」が 3 で「う」が 2 ですか？ 仕様がよくわかりません。

[can110]

列２の数値の意味は何ですか？ また、列１の「あえ」が列２で「1」になっているのはどういうことを表していますか？

[midsum0323]

＞「い」が 3 で「う」が 2 ですか？ 仕様がよくわかりません。
「う」は３でした。失礼いたしました。
＞列２の数値の意味は何ですか？
列１は組み合わせで、列2はその組み合わせを含む文字列の数です。たとえば「あう」の場合「あ」と「う」を含む文字列は「あいう」と「あうえ」の２つあるので２となります。説明不足ですみません。

[KojiDoi]

よく読めば読むほどわからない質問文ですね。「文字列のなかに存在する文字」ここでいう「文字列」は列1に列挙してあるものですか、別のものですか？ 「文字」は列1に列挙してあるものですか、別のものですか？　列2は質問と関係あるデータですか、関係ないデータですか？

[KojiDoi]

「列１は組み合わせで、列2はその組み合わせを含む文字列の数です。」それなら「あ」は５じゃないの？ ますますわからないよ。

[midsum0323]

説明不足ですみません。質問文を書き換えました。

[can110]

おおむね理解できたと思います。さらに「ああ」や「あうあ」のような同じ文字を複数含む文字列も考慮すべきですか？

[midsum0323]

考慮していただけるとありがたいです

Answer 1

ちょっと要求を正確に理解できているかどうかわからないのですが、つまりは1～n（n=文字数長）のn-gramがぜんぶ欲しいということですか？

>>> s = "あいうえお"
>>> lst = []
>>> for i in range(1, len(s)+1):
...     for j in range(len(s)-i+1):
...         lst.append(s[j:j+i])
... 
>>> lst
['あ', 'い', 'う', 'え', 'お', 'あい', 'いう', 'うえ', 'えお', 'あいう', 'いうえ', 'うえお', 'あいうえ', 'いうえお', 'あいうえお']

追記

要求を理解できたので、素直に書いてみました。

from itertools import chain,  combinations

lst = ["あいう", "あうえ", "い", "うい"]
def make_combi(s):
    s_set = set(s)
    result = []
    for i in range(len(s_set)):
        result.extend(sorted([tuple(sorted(x)) for x in combinations(s_set, i+1)]))
    return result

combi_result = [make_combi(s) for s in lst]
chained_data = list(chain.from_iterable(combi_result))
index = sorted(list(set(chained_data)))
result = [(key, chained_data.count(key)) for key in index]

for key, val in result:
    print(key, val)
"""結果
('あ',) 2
('あ', 'い') 1
('あ', 'い', 'う') 1
('あ', 'う') 2
('あ', 'う', 'え') 1
('あ', 'え') 1
('い',) 3
('い', 'う') 2
('う',) 3
('う', 'え') 1
('え',) 1
"""

数十万件だとそのまま使うのは厳しいかもしれません。うまいやり方を考えるのは他の方に譲ります（あるいはご自身でどうぞ）。

Comments

[midsum0323]

ご回答ありがとうございます。説明不足で恐縮ですが、Ngramではありません。
「あいうえお」の場合、「いえお」とか「あお」のパターンも数えたいです。

[hayataka2049]

やりたいことは概ね理解できました（と思います）。異なり文字の組み合わせを列挙し（1～異なり文字数まで取り出す）、それでindexを作って出現する文書の数をカウントする、で合っていますか？

[midsum0323]

そうです！

[hayataka2049]

追記しました

[midsum0323]

ありがとうございます。試してみます。

[hayataka2049]

1文中の重複はハナから無視しているので、chained_dataをdefaultdictでも使って数えれば速度はなんとかなる気がしてきました。これだとリストの走査が一回で済むので、count使うよりはだいぶマシ（なはず）です。
d = defaultdict(int)
for x in chained_data:
d[x] += 1

[hayataka2049]

質問の追記・修正依頼で上がっている複数含む文字列を考慮するというのは、(あ,あ)という要素も対象にカウントするということですか？　それだと私のコードは対応していないことをお知らせしておきます。対応させたい場合は、make_combiの一行目でsetにしているのをやめてください。

[midsum0323]

コメントありがとうございます。助かります

Answer 2

集計する際、Counterを使うと、便利だと思います。

from collections import Counter
from itertools import chain, combinations

def realset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(1:len(s)+1))

words = ["あいう", "あうえ", "い", "うい"]

res = Counter()
for count in [Counter(realset(x)) for x in words]:
    res += count

for key, value in res.items():
    print(key,value)

Answer 3

reでANDマッチングしてみました。

import re
from itertools import combinations


def make_charsets(words):
    chars = sorted(set(''.join(words)))
    charset_map = [
        list(combinations(chars, i))
        for i in range(1, len(chars) + 1)
    ]
    return [charset for line in charset_map for charset in line]


def match_andpattern(charset):
    andpattern = '^' + ''.join(['(?=.*' + c + ')' for c in charset])

    def _match(word):
        return re.match(andpattern, word) != None

    return _match


def count_matching(charset, words):
    return (charset, len(list(filter(match_andpattern(charset), words))))


words = ["あいう", "あうえ", "い", "うい"]
charset_list = make_charsets(words)
count_list = [count_matching(charset, words) for charset in charset_list]
after = list(map(print, filter(lambda x: x[1] != 0, count_list)))

Comments

[arch_]

ロジックがアレでした。

Answer 4

素直に組むなら各文字列について1～N個の組み合わせを生成して既存分とチェックする感じですかね。
速度的にどうかですが。

なお「あああ」のように同じ文字を複数含む場合も考慮しています。

import itertools

lines = ['あいう','あうえ','い','うい']
lines = [''.join( sorted(line)) for line in lines]# 文字の並びは関係ないので最初に昇順に

combs = {} # キー：各文字列に出現しうる文字の組み合わせ
           # 値  ：出現した文字列の位置の集合。要素数＝出現数

for idx, line in enumerate( lines):
    # N文字から 1...N文字でできる組み合わせ
    for n in range(len(line)):
        for i in itertools.combinations(line,n+1):
            if i not in combs:
                combs[i] = set()
            combs[i].add(idx)

for k,v in combs.items():
    print('{} ->{}個'.format(k,len(v)))

Comments

[midsum0323]

ありがとうございます。試してみます

Answer 5

たとえば、文字列Xが"a","b","c"の3文字をすべて含んでいるか否かは、次のコードで確認できます。

import re
r = re.search("(?=.*a)(?=.*b)(?=.*c)", x)

上記abcにあたるものを「パターン」から持ってきて、rがNonoTypeでないならカウンタを+1する。そういうループを組めばいいのではないでしょうか。