위키 레이싱 문서 그래프

문서별 연결 보기

전체 파일은 이 페이지에 담기에 커서 문서 2,003개만 넣었다. 들어오는 링크가 많은 문서 1,500개, 무작위 문서 500개, 예시 문서로 골랐다. 파란 칸을 누르면 그 문서로 이동하고, 회색 칸은 표본에 없는 문서다.

전처리 결과 파일

문서마다 0부터 770,113까지 번호를 매기고, 제목과 링크를 파일 두 개로 나눴다. 자료구조를 바꿔도 모두 이 파일을 읽는다.

links.txt의 n번째 줄(0부터)이 n번 문서다. 대상 번호는 오름차순이고 겹치지 않으며, 나가는 링크가 없는 문서 2,967개는 번호만 있는 줄로 남아 있다. 두 파일을 다시 읽어 문서 수, 링크 수, 번호 범위와 순서를 검사했고 모두 통과했다.

전처리 코드

덤프 4개를 읽어 위 파일 두 개를 만든다. 이 PC에서 약 3분 걸렸고, 표준 라이브러리만 쓴다.

python -I scripts/preprocess.py data/raw data/processed

"""덤프 4개를 문서 번호 기반 그래프 파일로 바꾼다.

사용법: python -I scripts/preprocess.py <덤프 폴더> <출력 폴더>

출력
  titles.tsv : 줄마다 "번호<TAB>page_id<TAB>제목". 번호는 0부터 빈틈없이 매긴다.
  links.txt  : 줄마다 "출발번호 대상번호 대상번호 ...". 출발번호 순서이고, 대상번호는 오름차순이며 겹치지 않는다.
               나가는 링크가 없는 문서도 번호만 있는 줄로 남긴다.
"""
import gzip
import re
import sys
import time
from array import array
from pathlib import Path

STR = rb"'((?:[^'\\]|\\.)*)'"
OPT = rb"(NULL|'(?:[^'\\]|\\.)*')"
RX_PAGE = re.compile(rb"\((\d+),(-?\d+)," + STR + rb",(\d),", re.S)
RX_REDIRECT = re.compile(rb"\((\d+),(-?\d+)," + STR + rb"," + OPT + rb",", re.S)
RX_LINKTARGET = re.compile(rb"\((\d+),(-?\d+)," + STR + rb"\)", re.S)
RX_PAGELINKS = re.compile(rb"\((\d+),(-?\d+),(\d+)\)")


def unescape(raw):
    return re.sub(rb"\\(.)", lambda m: m[1], raw, flags=re.S)


def rows(path, rx):
    """INSERT 아래의 행(한 줄에 한 행)을 읽는다. 해석 못 하는 줄이 있으면 바로 멈춘다."""
    in_insert = False
    with gzip.open(path, "rb") as f:
        for line in f:
            if in_insert and line[:1] == b"(":
                m = rx.match(line)
                if m is None:
                    raise ValueError(f"해석 실패 {path}: {line[:200]!r}")
                yield m
                continue
            in_insert = line.startswith(b"INSERT INTO")


def main(raw_dir, out_dir):
    t0 = time.time()
    log = lambda msg: print(f"[{time.time() - t0:7.1f}s] {msg}", flush=True)
    raw, out = Path(raw_dir), Path(out_dir)
    out.mkdir(parents=True, exist_ok=True)

    # 1. page: 일반 문서(공간 0)의 제목과 넘겨주기 여부
    id_of, title_of, redirect_pages = {}, {}, set()
    for m in rows(raw / "kowiki-latest-page.sql.gz", RX_PAGE):
        if m[2] == b"0":
            pid, title = int(m[1]), unescape(m[3])
            id_of[title] = pid
            title_of[pid] = title
            if m[4] == b"1":
                redirect_pages.add(pid)
    log(f"page: 일반 문서 {len(title_of):,}개, 넘겨주기 {len(redirect_pages):,}개")

    # 2. redirect: 넘겨주기 문서 -> 진짜 문서
    rd = {}
    for m in rows(raw / "kowiki-latest-redirect.sql.gz", RX_REDIRECT):
        frm = int(m[1])
        if frm in title_of:
            rd[frm] = (int(m[2]), unescape(m[3]), m[4] not in (b"NULL", b"''"))

    def resolve(pid):
        seen = {pid}
        while True:
            t = rd.get(pid)
            if t is None or t[2] or t[0] != 0:
                return None
            nxt = id_of.get(t[1])
            if nxt is None:
                return None
            if nxt not in redirect_pages:
                return nxt
            if nxt in seen:
                return None
            seen.add(nxt)
            pid = nxt

    final = {p: resolve(p) for p in redirect_pages}
    log(f"redirect: 풀린 넘겨주기 {sum(v is not None for v in final.values()):,}개")

    # 3. 넘겨주기가 아닌 문서에 0부터 새 번호를 매긴다 (page_id 오름차순)
    articles = sorted(p for p in title_of if p not in redirect_pages)
    new_id = {p: i for i, p in enumerate(articles)}
    n = len(articles)
    with open(out / "titles.tsv", "w", encoding="utf-8", newline="\n") as f:
        for i, p in enumerate(articles):
            f.write(f"{i}\t{p}\t{title_of[p].decode('utf-8', 'replace')}\n")
    log(f"titles.tsv: {n:,}줄")

    # 4. linktarget: lt_id -> 새 번호 (문서로 이어지는 대상만)
    lt = {}
    for m in rows(raw / "kowiki-latest-linktarget.sql.gz", RX_LINKTARGET):
        if m[2] != b"0":
            continue
        pid = id_of.get(unescape(m[3]))
        if pid is None:
            continue
        dest = final.get(pid) if pid in redirect_pages else pid
        if dest is not None:
            lt[int(m[1])] = new_id[dest]
    log(f"linktarget: 문서로 이어지는 대상 {len(lt):,}개")
    del id_of, title_of, redirect_pages, rd, final

    # 5. pagelinks: (출발, 대상) 쌍으로 바꾼다. pl_from 순서가 아니므로 모아서 정렬한다.
    packed = array("Q")
    for m in rows(raw / "kowiki-latest-pagelinks.sql.gz", RX_PAGELINKS):
        if m[2] != b"0":
            continue
        src = new_id.get(int(m[1]))
        if src is None:
            continue
        dst = lt.get(int(m[3]))
        if dst is None or dst == src:
            continue
        packed.append(src << 32 | dst)
    log(f"pagelinks: 후보 {len(packed):,}개, 정렬 시작")
    del lt, new_id
    ordered = sorted(packed)
    del packed
    log("정렬 끝, links.txt 쓰는 중")

    # 6. 겹치는 쌍을 지우며 한 줄에 한 문서씩 쓴다
    edges = 0
    with open(out / "links.txt", "w", encoding="ascii", newline="\n", buffering=1 << 20) as f:
        cur, targets, last = 0, [], None
        for v in ordered:
            if v == last:
                continue
            last = v
            src = v >> 32
            while cur < src:
                f.write(" ".join([str(cur), *targets]) + "\n")
                cur, targets = cur + 1, []
            targets.append(str(v & 0xFFFFFFFF))
            edges += 1
        while cur < n:
            f.write(" ".join([str(cur), *targets]) + "\n")
            cur, targets = cur + 1, []
    log(f"links.txt: {n:,}줄, 간선 {edges:,}개")


if __name__ == "__main__":
    main(sys.argv[1], sys.argv[2])