［PHP］levenshtein関数完全マスター！文字列の類似度判定とあいまい検索の実装方法

PHP

はじめに

文字列の類似度を測定したり、タイポを許容した検索機能を実装したい場面はありませんか？PHPのlevenshtein関数は、2つの文字列間の編集距離（レーベンシュタイン距離）を計算する強力な機能です。

この記事では、levenshtein関数の基本的な使い方から、実際のWebアプリケーションでの活用例まで詳しく解説します。

levenshtein関数とは？

レーベンシュタイン距離（編集距離）は、一つの文字列を別の文字列に変換するために必要な最小の編集操作（挿入、削除、置換）の回数を表します。

基本構文

levenshtein(string $string1, string $string2): int
levenshtein(string $string1, string $string2, int $insertion_cost, int $replacement_cost, int $deletion_cost): int

パラメータ：

  • $string1: 比較する文字列1
  • $string2: 比較する文字列2
  • $insertion_cost: 挿入操作のコスト（デフォルト: 1）
  • $replacement_cost: 置換操作のコスト（デフォルト: 1）
  • $deletion_cost: 削除操作のコスト（デフォルト: 1）

戻り値：

  • 編集距離（整数値）
  • 文字列の長さが255文字を超える場合は -1

基本的な使用例

1. シンプルな文字列比較

<?php
// 基本的な使用例
$string1 = "apple";
$string2 = "aple";

$distance = levenshtein($string1, $string2);
echo "編集距離: {$distance}\n"; // 編集距離: 1

// より複雑な例
$examples = [
    ['cat', 'bat'],      // 1文字置換 → 距離: 1
    ['kitten', 'sitting'], // 複数操作 → 距離: 3
    ['hello', 'hallo'],   // 1文字置換 → 距離: 1
    ['world', ''],        // 5文字削除 → 距離: 5
];

foreach ($examples as [$str1, $str2]) {
    $dist = levenshtein($str1, $str2);
    echo "'{$str1}' と '{$str2}' の距離: {$dist}\n";
}
?>

2. カスタムコストの設定

<?php
// カスタムコストの例
$string1 = "hello";
$string2 = "helo";

// デフォルトコスト（全て1）
$defaultDistance = levenshtein($string1, $string2);
echo "デフォルト距離: {$defaultDistance}\n"; // 1

// カスタムコスト（削除を重く評価）
$customDistance = levenshtein(
    $string1, 
    $string2,
    1,  // 挿入コスト
    2,  // 置換コスト  
    3   // 削除コスト
);
echo "カスタム距離: {$customDistance}\n"; // 3

// 実用例：タイポの種類に応じた重み付け
function calculateTypoDistance($original, $input) {
    return levenshtein(
        $original,
        $input,
        1,  // 挿入（文字の追加ミス）
        1,  // 置換（打ち間違い）
        2   // 削除（文字の脱落、より重いペナルティ）
    );
}

echo "タイポ距離: " . calculateTypoDistance("programming", "programing") . "\n"; // 2
?>

実践的な活用例

1. あいまい検索機能の実装

<?php
class FuzzySearch {
    private $data;
    private $threshold;
    
    public function __construct($data, $threshold = 3) {
        $this->data = $data;
        $this->threshold = $threshold;
    }
    
    public function search($query, $limit = 10) {
        $results = [];
        
        foreach ($this->data as $item) {
            $distance = levenshtein(
                strtolower($query), 
                strtolower($item)
            );
            
            // 閾値以下の場合のみ結果に含める
            if ($distance <= $this->threshold) {
                $results[] = [
                    'item' => $item,
                    'distance' => $distance,
                    'similarity' => $this->calculateSimilarity($query, $item, $distance)
                ];
            }
        }
        
        // 距離でソート（近い順）
        usort($results, function($a, $b) {
            return $a['distance'] <=> $b['distance'];
        });
        
        return array_slice($results, 0, $limit);
    }
    
    private function calculateSimilarity($str1, $str2, $distance) {
        $maxLength = max(strlen($str1), strlen($str2));
        return $maxLength > 0 ? (1 - $distance / $maxLength) * 100 : 100;
    }
    
    public function findBestMatch($query) {
        $bestMatch = null;
        $bestDistance = PHP_INT_MAX;
        
        foreach ($this->data as $item) {
            $distance = levenshtein(
                strtolower($query), 
                strtolower($item)
            );
            
            if ($distance < $bestDistance) {
                $bestDistance = $distance;
                $bestMatch = [
                    'item' => $item,
                    'distance' => $distance,
                    'similarity' => $this->calculateSimilarity($query, $item, $distance)
                ];
            }
        }
        
        return $bestMatch;
    }
}

// 使用例
$products = [
    'iPhone 15 Pro Max',
    'Samsung Galaxy S24',
    'Google Pixel 8',
    'MacBook Pro M3',
    'iPad Air',
    'Apple Watch Series 9',
    'AirPods Pro',
    'Surface Laptop'
];

$fuzzySearch = new FuzzySearch($products, 5);

// あいまい検索
$query = "iphone pro max";
$results = $fuzzySearch->search($query);

echo "検索クエリ: '{$query}'\n";
echo "検索結果:\n";
foreach ($results as $result) {
    printf("- %s (距離: %d, 類似度: %.1f%%)\n", 
        $result['item'], 
        $result['distance'], 
        $result['similarity']
    );
}

// 最適マッチの検索
$bestMatch = $fuzzySearch->findBestMatch("macbok pro");
if ($bestMatch) {
    printf("\n最適マッチ: %s (距離: %d, 類似度: %.1f%%)\n", 
        $bestMatch['item'], 
        $bestMatch['distance'], 
        $bestMatch['similarity']
    );
}
?>

2. スペルチェッカーの実装

<?php
class SpellChecker {
    private $dictionary;
    
    public function __construct($dictionaryFile) {
        $this->dictionary = $this->loadDictionary($dictionaryFile);
    }
    
    private function loadDictionary($file) {
        if (file_exists($file)) {
            return array_map('trim', file($file, FILE_IGNORE_NEW_LINES));
        }
        
        // デモ用の簡易辞書
        return [
            'apple', 'application', 'apply', 'appreciate',
            'hello', 'world', 'programming', 'developer',
            'computer', 'software', 'hardware', 'network',
            'database', 'algorithm', 'function', 'variable'
        ];
    }
    
    public function check($word) {
        $word = strtolower(trim($word));
        
        // 完全一致の場合
        if (in_array($word, $this->dictionary)) {
            return [
                'correct' => true,
                'word' => $word,
                'suggestions' => []
            ];
        }
        
        // スペルミスの可能性がある場合、候補を提案
        $suggestions = $this->getSuggestions($word, 3);
        
        return [
            'correct' => false,
            'word' => $word,
            'suggestions' => $suggestions
        ];
    }
    
    private function getSuggestions($word, $maxDistance = 2, $maxSuggestions = 5) {
        $suggestions = [];
        
        foreach ($this->dictionary as $dictWord) {
            $distance = levenshtein($word, $dictWord);
            
            if ($distance <= $maxDistance && $distance > 0) {
                $suggestions[] = [
                    'word' => $dictWord,
                    'distance' => $distance
                ];
            }
        }
        
        // 距離でソート
        usort($suggestions, function($a, $b) {
            return $a['distance'] <=> $b['distance'];
        });
        
        return array_slice($suggestions, 0, $maxSuggestions);
    }
    
    public function checkText($text) {
        $words = preg_split('/\s+/', $text);
        $results = [];
        
        foreach ($words as $word) {
            // 句読点を除去
            $cleanWord = preg_replace('/[^\w]/', '', $word);
            if (!empty($cleanWord)) {
                $results[$word] = $this->check($cleanWord);
            }
        }
        
        return $results;
    }
}

// 使用例
$spellChecker = new SpellChecker('dictionary.txt');

// 単語チェック
$testWords = ['aple', 'progaming', 'compter', 'netwerk'];

echo "単語スペルチェック:\n";
foreach ($testWords as $word) {
    $result = $spellChecker->check($word);
    
    if ($result['correct']) {
        echo "✓ '{$word}' は正しいスペルです\n";
    } else {
        echo "✗ '{$word}' はスペルミスの可能性があります\n";
        if (!empty($result['suggestions'])) {
            echo "  候補: ";
            $suggestions = array_column($result['suggestions'], 'word');
            echo implode(', ', $suggestions) . "\n";
        }
    }
}

// テキスト全体のチェック
$text = "I like aples and progaming compters.";
echo "\nテキストチェック: '{$text}'\n";
$textResults = $spellChecker->checkText($text);

foreach ($textResults as $originalWord => $result) {
    if (!$result['correct'] && !empty($result['suggestions'])) {
        $suggestion = $result['suggestions'][0]['word'];
        echo "'{$originalWord}' → '{$suggestion}' に修正を提案\n";
    }
}
?>

3. ユーザー名の重複チェック

<?php
class UsernameSimilarityChecker {
    private $existingUsernames;
    private $minDistance;
    
    public function __construct($existingUsernames, $minDistance = 2) {
        $this->existingUsernames = array_map('strtolower', $existingUsernames);
        $this->minDistance = $minDistance;
    }
    
    public function checkUsername($newUsername) {
        $newUsername = strtolower(trim($newUsername));
        $similarUsernames = [];
        
        foreach ($this->existingUsernames as $existing) {
            $distance = levenshtein($newUsername, $existing);
            
            if ($distance == 0) {
                return [
                    'available' => false,
                    'reason' => 'exact_match',
                    'message' => 'このユーザー名は既に使用されています',
                    'similar' => []
                ];
            }
            
            if ($distance < $this->minDistance) {
                $similarUsernames[] = [
                    'username' => $existing,
                    'distance' => $distance
                ];
            }
        }
        
        if (!empty($similarUsernames)) {
            usort($similarUsernames, function($a, $b) {
                return $a['distance'] <=> $b['distance'];
            });
            
            return [
                'available' => false,
                'reason' => 'too_similar',
                'message' => '類似したユーザー名が既に存在します',
                'similar' => array_slice($similarUsernames, 0, 3)
            ];
        }
        
        return [
            'available' => true,
            'reason' => 'available',
            'message' => 'このユーザー名は利用可能です',
            'similar' => []
        ];
    }
    
    public function suggestAlternatives($baseUsername, $count = 5) {
        $suggestions = [];
        $baseUsername = strtolower(trim($baseUsername));
        
        // 数字を付加した候補
        for ($i = 1; $i <= $count; $i++) {
            $candidate = $baseUsername . $i;
            if ($this->checkUsername($candidate)['available']) {
                $suggestions[] = $candidate;
            }
        }
        
        // アンダースコアを付加した候補
        $candidate = $baseUsername . '_';
        if ($this->checkUsername($candidate)['available']) {
            $suggestions[] = $candidate;
        }
        
        // 文字を追加した候補
        $suffixes = ['x', 'pro', 'dev', 'user'];
        foreach ($suffixes as $suffix) {
            $candidate = $baseUsername . $suffix;
            if ($this->checkUsername($candidate)['available'] && count($suggestions) < $count) {
                $suggestions[] = $candidate;
            }
        }
        
        return array_slice($suggestions, 0, $count);
    }
}

// 使用例
$existingUsernames = [
    'johndoe', 'janedoe', 'admin', 'user123', 
    'developer', 'programmer', 'webmaster', 'alice',
    'bob', 'charlie', 'davidsmith', 'maryjones'
];

$checker = new UsernameSimilarityChecker($existingUsernames, 3);

$testUsernames = ['johndo', 'johndoe', 'newuser', 'alice1', 'programmr'];

echo "ユーザー名チェック結果:\n";
foreach ($testUsernames as $username) {
    $result = $checker->checkUsername($username);
    
    echo "\n'{$username}': {$result['message']}\n";
    
    if (!$result['available']) {
        if (!empty($result['similar'])) {
            echo "類似ユーザー名: ";
            foreach ($result['similar'] as $similar) {
                echo "{$similar['username']} (距離:{$similar['distance']}) ";
            }
            echo "\n";
        }
        
        // 代替案を提案
        $alternatives = $checker->suggestAlternatives($username);
        if (!empty($alternatives)) {
            echo "代替案: " . implode(', ', $alternatives) . "\n";
        }
    }
}
?>

4. 検索候補システム

<?php
class SearchSuggestionSystem {
    private $searchIndex;
    private $popularQueries;
    
    public function __construct() {
        $this->searchIndex = [];
        $this->popularQueries = [];
    }
    
    public function addToIndex($terms) {
        $this->searchIndex = array_merge($this->searchIndex, $terms);
        $this->searchIndex = array_unique($this->searchIndex);
    }
    
    public function addPopularQuery($query, $count = 1) {
        $query = strtolower(trim($query));
        
        if (isset($this->popularQueries[$query])) {
            $this->popularQueries[$query] += $count;
        } else {
            $this->popularQueries[$query] = $count;
        }
        
        // 人気順でソート
        arsort($this->popularQueries);
    }
    
    public function getSuggestions($query, $maxSuggestions = 10) {
        $query = strtolower(trim($query));
        $suggestions = [];
        
        // 完全一致または前方一致の候補
        foreach ($this->searchIndex as $term) {
            $lowerTerm = strtolower($term);
            
            if ($lowerTerm === $query) {
                continue; // 完全一致は除外
            }
            
            if (strpos($lowerTerm, $query) === 0) {
                $suggestions[] = [
                    'term' => $term,
                    'type' => 'prefix_match',
                    'score' => 100,
                    'distance' => 0
                ];
            }
        }
        
        // レーベンシュタイン距離による候補
        foreach ($this->searchIndex as $term) {
            $distance = levenshtein($query, strtolower($term));
            
            if ($distance > 0 && $distance <= 3) {
                $score = max(0, 100 - ($distance * 20));
                
                $suggestions[] = [
                    'term' => $term,
                    'type' => 'fuzzy_match',
                    'score' => $score,
                    'distance' => $distance
                ];
            }
        }
        
        // 人気クエリからの候補
        foreach ($this->popularQueries as $popularQuery => $count) {
            $distance = levenshtein($query, $popularQuery);
            
            if ($distance > 0 && $distance <= 2) {
                $score = max(0, 90 - ($distance * 15)) + min($count, 20);
                
                $suggestions[] = [
                    'term' => $popularQuery,
                    'type' => 'popular_query',
                    'score' => $score,
                    'distance' => $distance
                ];
            }
        }
        
        // 重複を除去
        $uniqueSuggestions = [];
        foreach ($suggestions as $suggestion) {
            $key = strtolower($suggestion['term']);
            if (!isset($uniqueSuggestions[$key]) || 
                $uniqueSuggestions[$key]['score'] < $suggestion['score']) {
                $uniqueSuggestions[$key] = $suggestion;
            }
        }
        
        // スコア順でソート
        usort($uniqueSuggestions, function($a, $b) {
            return $b['score'] <=> $a['score'];
        });
        
        return array_slice($uniqueSuggestions, 0, $maxSuggestions);
    }
}

// 使用例
$suggestionSystem = new SearchSuggestionSystem();

// 検索インデックスに用語を追加
$terms = [
    'JavaScript', 'Java', 'Python', 'PHP', 'Ruby', 'Go', 'Rust',
    'React', 'Vue.js', 'Angular', 'Node.js', 'Express',
    'MySQL', 'PostgreSQL', 'MongoDB', 'Redis',
    'Docker', 'Kubernetes', 'AWS', 'Azure', 'GCP'
];

$suggestionSystem->addToIndex($terms);

// 人気クエリを追加
$popularQueries = [
    'javascript tutorial' => 150,
    'python basics' => 120,
    'react components' => 90,
    'php functions' => 80,
    'mysql queries' => 70
];

foreach ($popularQueries as $query => $count) {
    $suggestionSystem->addPopularQuery($query, $count);
}

// 検索候補のテスト
$testQueries = ['javasript', 'phyton', 'react', 'mysq', 'dockerr'];

echo "検索候補システムのテスト:\n";
foreach ($testQueries as $query) {
    echo "\n検索クエリ: '{$query}'\n";
    $suggestions = $suggestionSystem->getSuggestions($query, 5);
    
    if (empty($suggestions)) {
        echo "候補が見つかりませんでした\n";
    } else {
        echo "候補:\n";
        foreach ($suggestions as $suggestion) {
            printf("  %s (タイプ: %s, スコア: %d)\n", 
                $suggestion['term'], 
                $suggestion['type'], 
                $suggestion['score']
            );
        }
    }
}
?>

パフォーマンスの最適化

1. 大量データでの効率的な処理

<?php
class OptimizedLevenshtein {
    
    public static function fastLevenshtein($str1, $str2, $maxDistance = null) {
        $len1 = strlen($str1);
        $len2 = strlen($str2);
        
        // 長さの差が最大距離を超える場合は早期リターン
        if ($maxDistance !== null && abs($len1 - $len2) > $maxDistance) {
            return $maxDistance + 1;
        }
        
        // 短い文字列を最初に配置
        if ($len1 > $len2) {
            return self::fastLevenshtein($str2, $str1, $maxDistance);
        }
        
        // 空文字列の場合
        if ($len1 === 0) {
            return $len2;
        }
        
        // 通常のlevenshtein計算
        return levenshtein($str1, $str2);
    }
    
    public static function batchSearch($query, $targets, $threshold = 3) {
        $results = [];
        $queryLen = strlen($query);
        
        foreach ($targets as $target) {
            $targetLen = strlen($target);
            
            // 長さベースの事前フィルタリング
            if (abs($queryLen - $targetLen) > $threshold) {
                continue;
            }
            
            $distance = self::fastLevenshtein($query, $target, $threshold);
            
            if ($distance <= $threshold) {
                $results[] = [
                    'target' => $target,
                    'distance' => $distance
                ];
            }
        }
        
        return $results;
    }
}

// パフォーマンステスト
$targets = [];
for ($i = 0; $i < 10000; $i++) {
    $targets[] = 'word_' . $i . '_' . substr(md5($i), 0, 8);
}

$query = 'word_5000_abcd1234';

$start = microtime(true);
$results = OptimizedLevenshtein::batchSearch($query, $targets, 2);
$end = microtime(true);

echo "処理時間: " . number_format(($end - $start) * 1000, 2) . "ms\n";
echo "結果数: " . count($results) . "\n";
?>

2. メモ化による最適化

<?php
class MemoizedLevenshtein {
    private static $cache = [];
    private static $maxCacheSize = 10000;
    
    public static function distance($str1, $str2) {
        // キャッシュキーの生成
        $key = $str1 . '|' . $str2;
        
        if (isset(self::$cache[$key])) {
            return self::$cache[$key];
        }
        
        // キャッシュサイズの制限
        if (count(self::$cache) >= self::$maxCacheSize) {
            self::$cache = array_slice(self::$cache, -5000, null, true);
        }
        
        $distance = levenshtein($str1, $str2);
        self::$cache[$key] = $distance;
        
        return $distance;
    }
    
    public static function clearCache() {
        self::$cache = [];
    }
    
    public static function getCacheStats() {
        return [
            'cache_size' => count(self::$cache),
            'max_cache_size' => self::$maxCacheSize
        ];
    }
}
?>

制限事項と対処法

1. 文字列長の制限

<?php
function safeLevenshtein($str1, $str2) {
    $maxLength = 255;
    
    // 文字列が長すぎる場合の対処
    if (strlen($str1) > $maxLength || strlen($str2) > $maxLength) {
        // 先頭部分を比較
        $truncated1 = substr($str1, 0, $maxLength);
        $truncated2 = substr($str2, 0, $maxLength);
        
        return [
            'distance' => levenshtein($truncated1, $truncated2),
            'truncated' => true,
            'original_lengths' => [strlen($str1), strlen($str2)]
        ];
    }
    
    return [
        'distance' => levenshtein($str1, $str2),
        'truncated' => false,
        'original_lengths' => [strlen($str1), strlen($str2)]
    ];
}

// 長い文字列のテスト
$longStr1 = str_repeat('a', 300) . 'test';
$longStr2 = str_repeat('a', 300) . 'text';

$result = safeLevenshtein($longStr1, $longStr2);
print_r($result);
?>

2. 日本語対応

<?php
function mbLevenshtein($str1, $str2, $encoding = 'UTF-8') {
    // マルチバイト文字列を文字の配列に分割
    $chars1 = mb_str_split($str1, 1, $encoding);
    $chars2 = mb_str_split($str2, 1, $encoding);
    
    // 文字数が255を超える場合の制限
    if (count($chars1) > 255 || count($chars2) > 255) {
        return -1;
    }
    
    // 配列を文字列に結合してlevenshtein関数を使用
    // （日本語の場合、文字化けする可能性があるため独自実装が推奨）
    return customLevenshtein($chars1, $chars2);
}

function customLevenshtein($arr1, $arr2) {
    $len1 = count($arr1);
    $len2 = count($arr2);
    
    // DP配列の初期化
    $matrix = array_fill(0, $len1 + 1, array_fill(0, $len2 + 1, 0));
    
    // 初期値設定
    for ($i = 0; $i <= $len1; $i++) {
        $matrix[$i][0] = $i;
    }
    for ($j = 0; $j <= $len2; $j++) {
        $matrix[0][$j] = $j;
    }
    
    // DP計算
    for ($i = 1; $i <= $len1; $i++) {
        for ($j = 1; $j <= $len2; $j++) {
            $cost = ($arr1[$i-1] === $arr2[$j-1]) ? 0 : 1;
            
            $matrix[$i][$j] = min(
                $matrix[$i-1][$j] + 1,      // 削除
                $matrix[$i][$j-1] + 1,      // 挿入
                $matrix[$i-1][$j-1] + $cost // 置換
            );
        }
    }
    
    return $matrix[$len1][$len2];
}

// 日本語のテスト
$japanese1 = "こんにちは";
$japanese2 = "こんばんは";

$distance = mbLevenshtein($japanese1, $japanese2);
echo "日本語の編集距離: {$distance}\n";
?>

まとめ

PHPのlevenshtein関数は、文字列の類似度判定やあいまい検索の実装において非常に有用な機能です。基本的な編集距離の計算から、実際のWebアプリケーションでの活用まで幅広い用途があります。

重要なポイント

  1. 基本機能 – 2つの文字列間の編集距離を効率的に計算
  2. カスタムコスト – 操作の種類に応じた重み付けが可能
  3. 制限事項 – 文字列長は255文字まで、マルチバイト文字は注意が必要
  4. 実用例 – あいまい検索、スペルチェック、ユーザー名チェックなど
  5. 最適化 – 大量データ処理時はキャッシュや事前フィルタリングを活用

適切に活用することで、ユーザビリティの高い検索機能や、堅牢な入力検証システムの構築が可能になります。特にECサイトの商品検索や、ユーザー登録システムなどで威力を発揮します。

タイトルとURLをコピーしました