PythonでUNIXスタイルのファイルパスを簡素化（正規化）する方法

はじめに

UNIXスタイルのファイルシステムでは、ファイルの絶対パスが与えられたとき、それを「正規パス（カノニカルパス）」へと簡素化する必要があります。UNIX形式のファイルシステムにおいて、単一のピリオド「.」は現在のディレクトリを表し、二重のピリオド「..」は一つ上の階層（親ディレクトリ）への移動を意味します。

正規パスには、以下のような性質が求められます。

• パスは必ずスラッシュ「/」で始まること
• ディレクトリ名同士の間には、スラッシュ「/」が1つだけ存在すること
• 最後のディレクトリ名が存在する場合、末尾にスラッシュ「/」を付けないこと
• 正規パスは、絶対パスを表す最短の文字列であること

たとえば、「/home/」「/../」「/home//user/」というパスが与えられた場合、それぞれ「/home」「/」「/home/user」へと変換されます。

アルゴリズムの手順

処理は以下のステップで行います。

• リスト st を用意し、最初の要素として「/」を入れておく
• 与えられたパスを区切り文字「/」で分割した文字列のリストを a とする
• a の各要素 i に対して以下を繰り返す
  • i が「..」の場合：st の長さが1より大きければ、st の末尾要素を削除する。そうでなければ何もせず続行する
  • i が「.」の場合：何もせず次へ進む
  • i が空文字列でない場合：「/ + i」を st に追加する
• st に要素が1つしか残っていない場合は「/」を返す
• そうでなければ、st 内のすべての要素を連結して返す

実装例

以下のPythonコードは、上記のアルゴリズムを実装したものです。リストをスタックのように扱い、パスの各セグメントを順番に処理していきます。

class Solution:
    def simplifyPath(self, a):
        st = ['/']
        a = a.split("/")
        for i in a:
            if i == '..':
                if len(st) > 1:
                    st.pop()
                else:
                    continue
            elif i == '.':
                continue
            elif i != '':
                st.append("/" + str(i))
        if len(st) == 1:
            return "/"
        return "".join(st[1:])

ob1 = Solution()
print(ob1.simplifyPath("/home/"))
print(ob1.simplifyPath("/../"))
print(ob1.simplifyPath("/home//user/"))

入力

"/home/"
"/../"
"/home//user/"

出力

/home
/
/home/user

まとめ

このアルゴリズムでは、パスを「/」で分割し、各セグメントをスタックとして管理することで、効率よく正規化できます。「..」による親ディレクトリへの移動は、スタックのポップ操作として自然に表現できるのがポイントです。計算量はパスの長さに対して線形時間 O(n) となります。

なお、実際の開発では os.path.normpath() や pathlib.Path.resolve() といった標準ライブラリを利用すれば同様の処理が簡単に行えますが、アルゴリズムの仕組みを深く理解したい場合や、コーディング面接の対策としては、このような自前実装のアプローチを学んでおくことが非常に有用です。