質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.75%

  • Python 3.x

    5278questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

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

解決済

回答 5

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 271

midsum0323

score 22

例えば下のような文字列がある場合
あいう
あうえ

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

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

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

環境
Python3.6

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • midsum0323

    2018/04/11 14:11

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

    キャンセル

  • can110

    2018/04/11 14:48

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

    キャンセル

  • midsum0323

    2018/04/11 14:52

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

    キャンセル

回答 5

+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
"""

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/04/11 14:01

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

    キャンセル

  • 2018/04/11 14:18

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

    キャンセル

  • 2018/04/11 14:20

    そうです!

    キャンセル

  • 2018/04/11 14:30

    追記しました

    キャンセル

  • 2018/04/11 14:56

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

    キャンセル

  • 2018/04/11 15:05

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

    キャンセル

  • 2018/04/11 15:11

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

    キャンセル

  • 2018/04/11 15:13

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

    キャンセル

checkベストアンサー

0

素直に組むなら各文字列について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)))

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/04/11 15:13

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

    キャンセル

0

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

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


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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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)))

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/04/11 16:38

    ロジックがアレでした。

    キャンセル

0

集計する際、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)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.75%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 解決済

    JVMのダンプファイル作成パスがおかしい件

    APサーバ起動時にオプションとして、ダンプファイルを作成するように引数を加えました(パスを/opt/tomcat/logs/jfr/としました。) $java -XX:+Un

  • 受付中

    異なるDB間のデータ取得について

    異なるDBに接続し、1つ目のsqlで取得したidを元に、2つ目のsqlを実行するような処理を書きたいのですが 2つのDBをまたいだシェルを作成して実行したいとき、接続先とパスワ

  • 解決済

    【DB】左右対称の友達関係のようなテーブルの設計

    前提・実現したいこと Twitterのような左右非対称(Aをフォローしても、自動的にAにフォローされるわけではない)な友達関係ではなく、完全に左右対称な(どちらかがフォローすれば

  • 解決済

    RubyonRails データベースで同じテーブルが莫大な数になってしまいます。

    前提・実現したいこと 現在、ドットインストールのようなアプリを制作中です。 ・HTML入門 resson01. HTMLとはなにか [理解度チャック] resson0

  • 解決済

    php abdbに関して

    Test test1 test2この三つのテーブルをleft joinさせる形で結合させたいのですがどうしたら行けますか?

  • 解決済

    サーバ側でのキャッシュ管理

    いつもお世話になっております。 webシステム開発初心者です。 今私は、4Dというものを使って十人ぐらいが一斉にアクセスできるwebシステムを作っていて その時のフォームデ

  • 解決済

    顧客の家族や資産を管理するDB設計について

    DB設計はまったくの素人です.   顧客の情報とその顧客の家族、資産を管理するDB設計を行わなくてはならないのですが、 どのように設計したら良いのでしょうか? 現在エクセルにて

  • 解決済

    Excelでキーワードの組み合わせを作成したいです

     前提・実現したいこと 以下の条件で、Excelでキーワードの組み合わせを作成したいです。 また 1.以下の条件で実現できるか否かを何ご相談させて下さい。 2.何通りの組み合わ

同じタグがついた質問を見る

  • Python 3.x

    5278questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。