l o w </w>       : 5
l o w e r </w>   : 2
n e w e s t </w> : 6
w i d e s t </w> : 3

l o w </w>        : 5
l o w e r </w>    : 2
n e w es t </w>   : 6
w i d es t </w>   : 3

l o w </w>        : 5
l o w e r </w>    : 2
n e w est </w>    : 6
w i d est </w>    : 3

l o w </w>        : 5
l o w e r </w>    : 2
n e w est</w>     : 6
w i d est</w>     : 3

import re
from collections import Counter, defaultdict

class BPETokenizer:
    """Byte Pair Encoding トークナイザのミニマル実装"""

    def __init__(self, num_merges=100):
        self.num_merges = num_merges
        self.merges = []  # マージルールの順序リスト
        self.vocab = set()

    def _get_word_freqs(self, corpus):
        """コーパスから単語頻度を取得し、文字に分解する"""
        word_freqs = Counter()
        for sentence in corpus:
            words = sentence.strip().split()
            for word in words:
                word_freqs[word] += 1
        # 各単語を文字のタプルに変換（末尾に </w> を追加）
        split_words = {}
        for word, freq in word_freqs.items():
            chars = tuple(list(word) + ["</w>"])
            split_words[chars] = freq
        return split_words

    def _get_pair_freqs(self, split_words):
        """隣接ペアの頻度を計算する"""
        pair_freqs = Counter()
        for chars, freq in split_words.items():
            for i in range(len(chars) - 1):
                pair_freqs[(chars[i], chars[i + 1])] += freq
        return pair_freqs

    def _merge_pair(self, pair, split_words):
        """指定されたペアをマージする"""
        new_split_words = {}
        merged = pair[0] + pair[1]
        for chars, freq in split_words.items():
            new_chars = []
            i = 0
            while i < len(chars):
                if i < len(chars) - 1 and chars[i] == pair[0] and chars[i + 1] == pair[1]:
                    new_chars.append(merged)
                    i += 2
                else:
                    new_chars.append(chars[i])
                    i += 1
            new_split_words[tuple(new_chars)] = freq
        return new_split_words

    def train(self, corpus):
        """BPE を学習する"""
        split_words = self._get_word_freqs(corpus)

        # 初期語彙を構築
        self.vocab = set()
        for chars in split_words.keys():
            for c in chars:
                self.vocab.add(c)

        print(f"初期語彙サイズ: {len(self.vocab)}")

        for step in range(self.num_merges):
            pair_freqs = self._get_pair_freqs(split_words)
            if not pair_freqs:
                break

            # 最頻ペアを選択
            best_pair = max(pair_freqs, key=pair_freqs.get)
            best_freq = pair_freqs[best_pair]

            # マージを実行
            split_words = self._merge_pair(best_pair, split_words)
            merged_token = best_pair[0] + best_pair[1]
            self.merges.append(best_pair)
            self.vocab.add(merged_token)

            if step < 10 or step % 20 == 0:
                print(f"ステップ {step + 1}: ({best_pair[0]}, {best_pair[1]}) -> "
                      f"{merged_token} (頻度: {best_freq})")

        print(f"最終語彙サイズ: {len(self.vocab)}")

    def encode(self, word):
        """単語をBPEトークン列に変換する"""
        tokens = list(word) + ["</w>"]

        for pair in self.merges:
            i = 0
            while i < len(tokens) - 1:
                if tokens[i] == pair[0] and tokens[i + 1] == pair[1]:
                    tokens = tokens[:i] + [pair[0] + pair[1]] + tokens[i + 2:]
                else:
                    i += 1
        return tokens


# BPE のデモ
corpus = [
    "low low low low low",
    "lower lower",
    "newest newest newest newest newest newest",
    "widest widest widest",
]

bpe = BPETokenizer(num_merges=15)
bpe.train(corpus)

print("\n--- エンコード例 ---")
for word in ["newest", "lowest", "newer"]:
    tokens = bpe.encode(word)
    print(f"{word} -> {tokens}")

import math
from collections import Counter

class WordPieceTokenizer:
    """WordPiece トークナイザのミニマル実装"""

    def __init__(self, num_merges=100):
        self.num_merges = num_merges
        self.vocab = set()
        self.merges = []

    def _get_word_freqs(self, corpus):
        """コーパスから単語頻度を取得"""
        word_freqs = Counter()
        for sentence in corpus:
            for word in sentence.strip().split():
                word_freqs[word] += 1
        split_words = {}
        for word, freq in word_freqs.items():
            chars = tuple(list(word) + ["</w>"])
            split_words[chars] = freq
        return split_words

    def _get_token_freqs(self, split_words):
        """各トークンの出現頻度を計算"""
        token_freqs = Counter()
        for chars, freq in split_words.items():
            for c in chars:
                token_freqs[c] += freq
        return token_freqs

    def _get_pair_scores(self, split_words):
        """PMI ベースのペアスコアを計算する"""
        pair_freqs = Counter()
        token_freqs = Counter()
        total = 0

        for chars, freq in split_words.items():
            for i in range(len(chars)):
                token_freqs[chars[i]] += freq
                total += freq
                if i < len(chars) - 1:
                    pair_freqs[(chars[i], chars[i + 1])] += freq

        # PMI スコア: log(P(ab) / (P(a) * P(b)))
        # P(ab) ∝ count(ab), P(a) ∝ count(a), P(b) ∝ count(b)
        # score = count(ab) / (count(a) * count(b)) に比例
        pair_scores = {}
        for pair, freq in pair_freqs.items():
            a, b = pair
            score = freq / (token_freqs[a] * token_freqs[b])
            pair_scores[pair] = score

        return pair_scores

    def _merge_pair(self, pair, split_words):
        """ペアをマージする"""
        new_split_words = {}
        merged = pair[0] + pair[1]
        for chars, freq in split_words.items():
            new_chars = []
            i = 0
            while i < len(chars):
                if i < len(chars) - 1 and chars[i] == pair[0] and chars[i + 1] == pair[1]:
                    new_chars.append(merged)
                    i += 2
                else:
                    new_chars.append(chars[i])
                    i += 1
            new_split_words[tuple(new_chars)] = freq
        return new_split_words

    def train(self, corpus):
        """WordPiece を学習する"""
        split_words = self._get_word_freqs(corpus)

        self.vocab = set()
        for chars in split_words.keys():
            for c in chars:
                self.vocab.add(c)

        print(f"初期語彙サイズ: {len(self.vocab)}")

        for step in range(self.num_merges):
            pair_scores = self._get_pair_scores(split_words)
            if not pair_scores:
                break

            best_pair = max(pair_scores, key=pair_scores.get)
            best_score = pair_scores[best_pair]

            split_words = self._merge_pair(best_pair, split_words)
            merged_token = best_pair[0] + best_pair[1]
            self.merges.append(best_pair)
            self.vocab.add(merged_token)

            if step < 10 or step % 20 == 0:
                print(f"ステップ {step + 1}: ({best_pair[0]}, {best_pair[1]}) -> "
                      f"{merged_token} (PMIスコア: {best_score:.6f})")

        print(f"最終語彙サイズ: {len(self.vocab)}")

    def encode(self, word):
        """最長一致法でエンコードする"""
        tokens = []
        chars = word + "</w>"
        start = 0
        while start < len(chars):
            end = len(chars)
            found = False
            while start < end:
                substr = chars[start:end]
                if start > 0:
                    substr = "##" + substr
                if substr.replace("##", "") in self.vocab or substr in self.vocab:
                    tokens.append(substr)
                    found = True
                    break
                end -= 1
            if not found:
                tokens.append("[UNK]")
                start += 1
            else:
                if start > 0:
                    start = end
                else:
                    start = end
        return tokens


# WordPiece のデモ
corpus = [
    "low low low low low",
    "lower lower",
    "newest newest newest newest newest newest",
    "widest widest widest",
]

wp = WordPieceTokenizer(num_merges=15)
wp.train(corpus)

print("\n--- WordPiece エンコード例 ---")
for word in ["newest", "lowest", "wider"]:
    tokens = wp.encode(word)
    print(f"{word} -> {tokens}")

import numpy as np
from collections import Counter

class UnigramTokenizer:
    """Unigram Language Model トークナイザのミニマル実装"""

    def __init__(self, target_vocab_size=50, max_piece_length=5):
        self.target_vocab_size = target_vocab_size
        self.max_piece_length = max_piece_length
        self.vocab = {}  # token -> log_prob

    def _initialize_vocab(self, corpus):
        """初期語彙を構築する（全サブストリングの頻度）"""
        substring_freqs = Counter()
        char_set = set()

        for sentence in corpus:
            for word in sentence.strip().split():
                word = word + "</w>"
                for i in range(len(word)):
                    for j in range(i + 1, min(i + self.max_piece_length + 1, len(word) + 1)):
                        substring_freqs[word[i:j]] += 1
                for c in word:
                    char_set.add(c)

        # 頻度の高いサブストリングを初期語彙とする
        total = sum(substring_freqs.values())
        self.vocab = {}
        for substr, freq in substring_freqs.most_common(self.target_vocab_size * 5):
            self.vocab[substr] = np.log(freq / total)

        # 個別の文字は必ず含める
        for c in char_set:
            if c not in self.vocab:
                self.vocab[c] = np.log(1e-10)

        self.char_set = char_set
        print(f"初期語彙サイズ: {len(self.vocab)}")

    def _viterbi_decode(self, text):
        """Viterbi アルゴリズムで最適分割を求める"""
        n = len(text)
        # dp[j] = 位置 j までの最適対数確率
        dp = [-float('inf')] * (n + 1)
        dp[0] = 0.0
        backpointer = [0] * (n + 1)

        for j in range(1, n + 1):
            for i in range(max(0, j - self.max_piece_length), j):
                piece = text[i:j]
                if piece in self.vocab:
                    score = dp[i] + self.vocab[piece]
                    if score > dp[j]:
                        dp[j] = score
                        backpointer[j] = i

        # バックトレース
        tokens = []
        j = n
        while j > 0:
            i = backpointer[j]
            tokens.append(text[i:j])
            j = i
        tokens.reverse()
        return tokens, dp[n]

    def _compute_loss(self, corpus_words):
        """各トークンを除いた場合の尤度減少量を計算する"""
        token_counts = Counter()
        total_log_prob = 0.0

        for word, freq in corpus_words.items():
            tokens, log_prob = self._viterbi_decode(word)
            total_log_prob += log_prob * freq
            for token in tokens:
                token_counts[token] += freq

        return token_counts, total_log_prob

    def train(self, corpus, n_iterations=5):
        """Unigram LM を学習する"""
        self._initialize_vocab(corpus)

        # コーパスの単語頻度
        word_freqs = Counter()
        for sentence in corpus:
            for word in sentence.strip().split():
                word_freqs[word + "</w>"] += 1

        for iteration in range(n_iterations):
            # E ステップ（Viterbi 近似）: 最適分割で各トークンの頻度を計算
            token_counts = Counter()
            total_log_prob = 0.0

            for word, freq in word_freqs.items():
                tokens, log_prob = self._viterbi_decode(word)
                total_log_prob += log_prob * freq
                for token in tokens:
                    token_counts[token] += freq

            # M ステップ: 確率を更新
            total_count = sum(token_counts.values())
            for token in self.vocab:
                if token in token_counts:
                    self.vocab[token] = np.log(token_counts[token] / total_count)
                else:
                    self.vocab[token] = np.log(1e-10)

            print(f"反復 {iteration + 1}: 対数尤度 = {total_log_prob:.2f}, "
                  f"語彙サイズ = {len(self.vocab)}")

            # 語彙の削減
            if len(self.vocab) > self.target_vocab_size:
                # 各トークンの loss を計算（簡易版: 頻度の低いトークンを削除）
                scored = []
                for token, log_prob in self.vocab.items():
                    # 単一文字は削除しない
                    if len(token) == 1 or token in self.char_set:
                        continue
                    count = token_counts.get(token, 0)
                    scored.append((token, count))

                # 頻度の低い順にソートして削除
                scored.sort(key=lambda x: x[1])
                n_remove = max(1, int(len(self.vocab) * 0.1))
                n_remove = min(n_remove, len(self.vocab) - self.target_vocab_size)

                for token, _ in scored[:n_remove]:
                    if len(self.vocab) <= self.target_vocab_size:
                        break
                    del self.vocab[token]

        print(f"最終語彙サイズ: {len(self.vocab)}")

    def encode(self, word):
        """Viterbi 分割でエンコードする"""
        word = word + "</w>"
        tokens, log_prob = self._viterbi_decode(word)
        return tokens


# Unigram LM のデモ
corpus = [
    "low low low low low",
    "lower lower",
    "newest newest newest newest newest newest",
    "widest widest widest",
    "new new new new",
    "wide wide wide",
]

unigram = UnigramTokenizer(target_vocab_size=30, max_piece_length=6)
unigram.train(corpus, n_iterations=10)

print("\n--- Unigram LM エンコード例 ---")
for word in ["newest", "lowest", "wider"]:
    tokens = unigram.encode(word)
    print(f"{word} -> {tokens}")

import numpy as np
import matplotlib.pyplot as plt

# 語彙サイズと OOV 率の関係をシミュレーション
np.random.seed(42)

# Zipf の法則に従う単語頻度を生成
n_words = 10000
ranks = np.arange(1, n_words + 1)
freqs = 1.0 / ranks
freqs /= freqs.sum()

# 累積カバレッジ
cumulative_coverage = np.cumsum(freqs)

# 異なる語彙サイズでのカバレッジ
vocab_sizes = [100, 500, 1000, 2000, 5000, 10000]

plt.figure(figsize=(10, 6))
plt.plot(ranks, cumulative_coverage * 100, 'b-', linewidth=2)
for vs in vocab_sizes:
    coverage = cumulative_coverage[vs - 1] * 100
    plt.axvline(x=vs, color='gray', linestyle='--', alpha=0.5)
    plt.annotate(f'|V|={vs}\n{coverage:.1f}%',
                xy=(vs, coverage), fontsize=8,
                xytext=(vs + 200, coverage - 5),
                arrowprops=dict(arrowstyle='->', color='red'))

plt.xlabel('Vocabulary Size', fontsize=12)
plt.ylabel('Corpus Coverage (%)', fontsize=12)
plt.title('Vocabulary Size vs Corpus Coverage (Zipf Distribution)', fontsize=14)
plt.xscale('log')
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()