Pythonで出現回数に基づいてフレーズを分類・並べ替えるプログラム

問題の概要

2つのリストが与えられているとします。1つは選び抜かれたフレーズを格納する「phrases」、もう1つは複数の文を格納する「sentences」です。sentences の各文には、phrases 内のフレーズが含まれることもあれば、含まれないこともあります。

目的は、phrases の各フレーズが sentences 内に何回出現するかを調べ、その出現回数に基づいて phrases を並べ替えることです。そして、並べ替え後のリスト「phrases」を出力として返します。

入力例と出力例

たとえば、入力が次のようになっているとします。

phrases = ['strong', 'durable', 'efficient']
sentences = ['the product is durable and efficient',
             'strong and durable',
             'it is efficient',
             'like it because it is efficient']

このときの出力は ['efficient', 'durable', 'strong'] となります。

結果の読み方

フレーズ「efficient」は、0番目・2番目・3番目の文に出現しており、合計3回と最も多いため、出力の先頭に置かれます。続く「durable」は0番目と1番目の文に2回、「strong」は1番目の文に1回出現しています。出現回数の多い順に並べることで、この順序が決まります。

解決のための手順

この問題は、次の手順に従って解くことができます。

• 出現回数を記録するマップ cnt を用意する。
• phrases 内の各フレーズ feature について、cnt[feature] を 0 で初期化する。
• sentences 内の各文 response について、次を繰り返す。
  • 文を単語に分割したリスト p を作成する。
  • p から重複を除いたセット s を作成する。
  • s 内の各単語 i について、i が cnt に存在すれば cnt[i] を 1 増やす。
• cnt の各キー k に対してペア (k, cnt[k]) を持つリスト res を作成する。
• res を出現回数の降順でソートする(同数の場合は元のリスト内の順序を優先)。
• カウント値を取り除き、フレーズ名だけのリストを返す。

実装例(Python)

理解を深めるために、実際の実装を見てみましょう。

def solve(phrases, sentences):
    cnt = {}
    for feature in phrases:
        cnt[feature] = 0
    for response in sentences:
        p = response.split()
        s = set(p)
        for i in s:
            if i in cnt:
                cnt[i] += 1
    res = [[k, cnt[k]] for k in cnt]
    res.sort(key=lambda x: (-x[1], phrases.index(x[0])))
    return [i[0] for i in res]

print(solve(['strong', 'durable', 'efficient'],
            ['the product is durable and efficient',
             'strong and durable',
             'it is efficient',
             'like it because it is efficient']))

入力

['strong', 'durable', 'efficient'],
['the product is durable and efficient', 'strong and durable',
 'it is efficient', 'like it because it is efficient']

出力

['efficient', 'durable', 'strong']

コードのポイント

• セット(set)を使う理由: 同じ文の中で同じ単語が何度登場しても、1回だけカウントされるようにするためです。これにより「1文につき1カウント」というルールが正しく守られます。
• ソートキーの工夫: -x[1] によって出現回数の降順に並べ替え、phrases.index(x[0]) によって出現回数が同じフレーズ同士は元のリストでの登場順を保ちます。これにより、常に安定した予測可能な結果が得られます。
• 計算量: 文の数を S、各文の平均単語数を W、フレーズ数を P とすると、全体の計算量はおおむね O(S×W + P log P) 程度に収まり、実用的な規模のデータであれば高速に動作します。