Pythonでテキスト内の2つの単語間の最小距離を求める方法を解説

はじめに

文字列処理の問題の中でも頻出するテーマの一つが、「文章中に出現する2つの単語の距離を求める」というものです。本記事では、Pythonを使って、テキスト（文）内に含まれる2つの単語 w1 と w2 の出現位置のうち、最も近いもの同士の距離を求めるプログラムを紹介します。

ここでの「距離」は、2つの単語の間に存在する単語数として定義します。また、どちらか一方の単語がテキスト中に存在しない場合は -1 を返す仕様とします。

問題の定義

3つの文字列 text、w1、w2 が与えられます。text は複数の単語から構成される文章です。このとき、w1 と w2 の任意の出現ペアの中で最小となる距離（間にある単語数）を求めてください。

例：

• text = "joy happy power happy joy joy power happy limit"
• w1 = "power"
• w2 = "limit"

この場合の出力は 1 になります。「power」と「limit」の間には単語「happy」が1つだけ存在するためです。

解法のアルゴリズム

この問題は、テキストを一度走査するだけで解くことができます。手順は以下の通りです。

1. index1 := null、index2 := null として初期化します（それぞれ w1、w2 の直近の出現位置を記録します）。
2. distance := 999999（十分に大きい値）で初期化します。
3. テキスト内の各インデックス idx と単語 w について以下を繰り返します。
   • w が w1 と一致する場合：index2 が null でなければ、distance を min(distance, |idx - index2| - 1) で更新し、index1 := idx を設定します。
   • w が w2 と一致する場合：index1 が null でなければ、distance を min(distance, |idx - index1| - 1) で更新し、index2 := idx を設定します。
4. ループ終了後、index1 と index2 の両方が null でなければ distance を返します。
5. それ以外の場合は -1 を返します。

ポイント

各単語の直近の出現位置だけを記録することで、すべての出現ペアを総当たりで調べる必要がなくなり、計算量は O(n) に抑えられます。これは効率的なアプローチです。

実装例

それでは、実際のPythonコードを見てみましょう。

def solve(text, w1, w2):
    index1 = None
    index2 = None
    distance = 2000000
    for idx, word in enumerate(text.split(" ")):
        if word == w1:
            if index2 is not None:
                distance = min(distance, abs(idx - index2) - 1)
            index1 = idx
        if word == w2:
            if index1 is not None:
                distance = min(distance, abs(idx - index1) - 1)
            index2 = idx
    if index1 is not None and index2 is not None:
        return distance
    return -1

text = "joy happy power happy joy joy power happy limit"
w1 = "power"
w2 = "limit"
print(solve(text, w1, w2))

入力

"joy happy power happy joy joy power happy limit", "power", "limit"

出力

1

コードの解説

まず、text.split(" ") によって文章を空白区切りで分割し、enumerate() で各単語とそのインデックスを順に取得します。

単語が w1 に一致したタイミングで、すでに w2 の出現位置（index2）が記録されていれば、その間の距離 |idx - index2| - 1 を計算し、現在の最小値と比較して更新します。w2 の場合も同様の処理を行います。-1 しているのは、距離を「間にある単語数」としてカウントするためです。

最後に、両方の単語が少なくとも1回出現していれば最小距離を返し、そうでなければ -1 を返します。

まとめ

このアルゴリズムは、テキストを線形に一度だけ走査すればよいため、時間計算量 O(n)、空間計算量 O(1)（split結果を除く）という非常に効率的な解法です。類似の問題として「文章中の最短距離にある同じ単語のペアを探す」問題などにも応用できるので、ぜひマスターしておきましょう。