【JavaScript】配列内で最も頻出する単語を上位N件抽出する方法

問題概要

英小文字のみで構成された文字列の配列 arr を第一引数として受け取り、数値 num（num は配列の長さより小さい値）を第二引数として受け取る JavaScript 関数を作成します。

この関数は、配列 arr 内で最も頻出する要素を上位 num 件返す必要があります。

結果は出現回数が多い順に並べます。また、出現回数が同じ単語が複数ある場合は、辞書順（アルファベット順）で先に来る単語を優先して並べます。

入力例

const arr = ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"];
const num = 4;

出力例

const output = ["the", "is", "sunny", "day"];

出力の説明

「the」「is」「sunny」「day」が出現回数の多い上位4つの単語です。それぞれの出現回数は 4回、3回、2回、1回 となっています。

実装コード

以下が実際のコードです。

const arr = ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"];
const num = 4;

const mostFrequent = (arr = [], num = 1) => {
    // 各単語の出現回数を記録するマップを作成
    const map = {};
    let keys = [];

    for (let i = 0; i < arr.length; i++) {
        if (map[arr[i]]) {
            map[arr[i]]++;
        } else {
            map[arr[i]] = 1;
        }
    }

    // マップのキー（単語）を配列にまとめる
    for (let i in map) {
        keys.push(i);
    }

    // 出現回数の降順でソートし、同数の場合は辞書順で昇順に
    keys = keys.sort((a, b) => {
        if (map[a] === map[b]) {
            if (a > b) {
                return 1;
            } else {
                return -1;
            }
        } else {
            return map[b] - map[a];
        }
    })
    .slice(0, num);

    return keys;
};

console.log(mostFrequent(arr, num));

実行結果

[ 'the', 'is', 'sunny', 'day' ]

コードの解説

このアルゴリズムは、大きく分けて次の3つのステップで構成されています。

ステップ1：出現回数の集計
まず、空のオブジェクト map を用意し、配列を1周しながら各単語の出現回数をカウントします。既にキーが存在すればインクリメントし、存在しなければ 1 をセットします。

ステップ2：キーの一覧化
for...in ループでマップのすべてのキー（単語）を配列 keys に格納します。

ステップ3：ソートと絞り込み
sort() の比較関数では、出現回数が異なる場合は回数の降順（map[b] - map[a]）で並べ替え、回数が同じ場合は文字列比較によって辞書順の昇順になるようにしています。最後に slice(0, num) で上位 num 件だけを取り出して返します。

計算量について

集計処理に O(n)、ソート処理に O(k log k)（k はユニークな単語数）かかるため、全体の計算量は O(n + k log k) となります。データ量が大きい場合でも十分に高速に動作する、効率的なアプローチです。