URL Normalization (HubSpot) - URLの正規化

どんな問題？

URL Normalization
http://www.checkio.org/mission/url-normalization/

以下のルールに則ってURLを正規化せよ。

URLを小文字にする。

%エスケープ文字は大文字にする。

デコード可能なエスケープ文字をデコードする。

デフォルトポートを削除。（httpなら80）

パスから、「..」や「.」を除去する。

引数のURLを正規化して、戻り値として返す。

例題：

checkio("Http://Www.Checkio.org") == "http://www.checkio.org"
checkio("http://www.checkio.org/%cc%b1bac") == "http://www.checkio.org/%CC%B1bac"
checkio("http://www.checkio.org/task%5F%31") == "http://www.checkio.org/task_1"
checkio("http://www.checkio.org:80/home/") == "http://www.checkio.org/home/"
checkio("http://www.checkio.org:8080/home/") == "http://www.checkio.org:8080/home/"
checkio("http://www.checkio.org/task/./1/../2/././name") == "http://www.checkio.org/task/2/name"

どうやって解く？

URLの分解

まず、URLを各パーツに分解する必要がある。
例えば、URLが "http://www.checkio.org:80/home/index.html" であれば、

scheme	http://
host	www.checkio.org
port	:80	省略可
path	/home/index.html	省略可

というように分解する。

正規表現を使ってみたが、かなり苦労した。どうも正規表現は苦手だなぁ。これでいけるはず。

url_pattern = re.compile(r'^(.+?)://(.+?)?(:\d+)?(/.*)?$')
scheme, host, port, path = [s or '' for s in url_pattern.match(url).groups()]

re.matchで見つからない場合は、Noneが返るので、''に変換している。

%エンコードの処理

こちらも正規表現の置換(sub)を使った。%00～%FFを検索して、見つかったら、置換用の関数 normalize_octets()を呼び出して、指定範囲内ならデコード、それ以外なら大文字化を行う。

def normalize_octets(match):
    s = match.group()
    i = int(s[1:], 16)
    if 0x41 <= i <= 0x5A or 0x61 <= i <= 0x7A or 0x30 <= i <= 0x39 or i in [0x2D, 0x2E, 0x5F, 0x7E]:
        return chr(i).lower()
    else:
        return s.upper()

path_pattern = re.compile(r'(%[\da-f]{2})', re.I)
path = path_pattern.sub(normalize_octets, path.lower())

pathも小文字化する必要があるので、デコード前のpathと、デコード後の文字(chr)も lower()で小文字化している。
（問題文ではわかりにくいが、pathが %48%6f%6d%45 の場合は、HomEではなくhomeにしなくてはならない。）

「.」と「..」の処理

簡単に処理する方法が思いつかなかったので、ディレクトリのリストを再構築するようにした。

def remove_dot_segments(path):
    dirs = []
    for d in path.split('/'):
        if d == '.':
            continue
        elif d == '..':
            if dirs:
                dirs.pop()
        else:
            dirs.append(d)
    return '/'.join(dirs)

まとめ

import re

def normalize_octets(match):
    s = match.group()
    i = int(s[1:], 16)
    if 0x41 <= i <= 0x5A or 0x61 <= i <= 0x7A or 0x30 <= i <= 0x39 or i in [0x2D, 0x2E, 0x5F, 0x7E]:
        return chr(i).lower()
    else:
        return s.upper()

def remove_dot_segments(path):
    dirs = []
    for d in path.split('/'):
        if d == '.':
            continue
        elif d == '..':
            if dirs:
                dirs.pop()
        else:
            dirs.append(d)
    return '/'.join(dirs)

def checkio(url):
    # Split URL
    url_pattern = re.compile(r'^(.+?)://(.+?)?(:\d+)?(/.*)?$')
    scheme, host, port, path = [s or '' for s in url_pattern.match(url).groups()]
    # Scheme and host to lower case
    scheme = scheme.lower()
    host = host.lower()
    # Remove default port
    if (scheme, port) == ('http', ":80"):
        port = ''
    # Normalize escape sequences
    path_pattern = re.compile(r'(%[\da-f]{2})', re.I)
    path = path_pattern.sub(normalize_octets, path.lower())
    # Remove '.' and '..'
    path = remove_dot_segments(path)
    # Make normalized URL
    return '{}://{}{}{}'.format(scheme, host, port, path)

http://www.checkio.org/mission/url-normalization/publications/natsuki/python-3/first/

特に難しい問題でもないのだが、ルールがよくわからず、Try&Errorを繰り返すことになってしまった。

summer_tree_home

Check iOでPython3をマスターするぜっ