根据已知字符串列表检查字符串中常见错误识别的字符 - Check for commonly mis-recognized characters in a string against a list of known strings

>Background

我的(MySQL(数据库中有一个代码列表，由六(6(个字符组成。它们由随机选择的数字和字母组成。它们被视为不区分大小写，但它们在数据库中以大写形式存储。它们可能包含数字0，但绝不包含字母O。我使用这些代码作为用户的一次性身份验证。

问题所在

这些代码是手写在卡片上的，不幸的是，某些字母和数字对某些人来说可能看起来很相似。这就是为什么我最初没有使用字母O因为它的外观与手写0非常接近。

到目前为止我做了什么

我能够根据用户输入检查代码(不敏感地(并确定它是否完全匹配。如果不是，我会默默地用0替换任何O，然后重试。

问题

我的问题是，我如何才能对其他字母和数字执行此操作，例如我在下面列出的字母和数字，并且仍然相对确信我没有将用户验证为他们不是的人？在这种情况下，代码中可以存在这两个字符。我已经查看了PHP(http://php.net/manual/en/function.levenshtein.php(和similar_text()(http://php.net/manual/en/function.similar-text.php(中的Levenshtein函数，但两者都不是我想要的，所以我想我可能不得不推出自己的(可能使用它们(来实现这一点。

相似人物：

S <=> 5
G <=> 6
I <=> 1

你描述的问题实际上是哈希冲突。您有多个可能的输入值，并且希望它们解析为单个明确的键。我在这里有几个想法。

正如@bishop所建议的，您真正需要确定的是任何给定的输入是否明确。不过，我的方法会略有不同：

对于任何给定的输入，我将生成所有可能的匹配键的列表，并在数据库中查询整个列表。如果只返回一个结果，则没有问题，您可以基于该单个记录继续。在这种情况下，用户输入 ABCDE5 或 ABCDES 并不重要，因为数据库中只有一个可能的匹配项。

但是，如果返回多个结果，则无法确定用户的输入是否准确或是否键入错误。

(事后看来，最好设计键，以便不可能出现任何模棱两可的字符对。例如，仅允许"S"和不允许"5"可以保证任何给定输入只有一个匹配项，无论用户键入"S">还是"5"，因为您始终可以安全地将您在输入中看到的任何 5 转换为 S，知道它们是输入错误。实际上，根据确切的值，您可以追溯修改数据库中的许多或所有键以遵循此规则，并使查找不那么麻烦。

无论如何，在这种模棱两可的情况下，我认为您别无选择，只能推回用户并要求他们重新检查他们的输入，希望在屏幕上的消息中解释可能的陷阱。

编辑：

下面是一个示例，用于根据用户实际提供的单个输入生成用户打算输入的可能值：

<?php
$inputs = [
        'ABCDEF', // No ambiguity, DB should return 0 or 1 match.
        'AAAAA1', // One ambiguous char, user could have meant `AAAAAI`
                  // instead so search DB for both.
        '156ISG', // Worst case. If the DB values overlap a lot, there
                  // wouldn't be much hope of "guessing" what the user
                  // actually meant.
];
foreach ($inputs as $input) {
    print_r(generatePossibleMatches($input));
}
//----------------------------------------
function generatePossibleMatches($input) {
    $input = strtoupper($input);
    $ambiguous = [
        'I' => '1',
        'G' => '6',
        'S' => '5',
    ];
    $possibles = [$input];
    foreach ($ambiguous as $letter => $number) {
        foreach ($possibles as $possible) {
            foreach (str_split($possible) as $pos => $char) {
                $addNumber = substr_replace($possible, $number, $pos, 1);
                $addLetter = substr_replace($possible, $letter, $pos, 1);
                if ($char === $letter && !in_array($addNumber, $possibles)) {
                    $possibles[] = $addNumber;
                }
                if ($char === $number && !in_array($addLetter, $possibles)) {
                    $possibles[] = $addLetter;
                }
            }
        }
    }
    return $possibles;
}

一种解决方案：将"令人困惑"的字符转换为与可能的替代字符匹配的正则表达式，然后将扩展的正则表达式与输入匹配。示例：如果输入为"AIX"，则正则表达式扩展将为"A[I1]X"。

法典：

$input = 'S1G6AB'; // given this
$store = '5I6GAB'; // need to match this
// convert each confusing character to a regular expression character class
$regex = implode('', array_map(function ($c) {
    $map = ['S'=>'[S5]','5'=>'[S5]','1'=>'[1I]','I'=>'[1I]','G'=>'[6G]','6'=>'[6G]'];
    return (array_key_exists($c, $map) ? $map[$c] : $c);
}, str_split($input)));
// match regex representing the input against the stored value    
echo (0 < preg_match("/$regex/", $store) ? 'Match' : 'No match');

在这里摆弄

显然，这假设任何给定输入的排列永远不会出现在多个记录中。如果用户 X 有"ABCDE1"，用户 Y 有"ABCDEI"，这将不起作用。

根据@beporter答案编辑构建

如果您的数据库支持正则表达式(如 MySQL(，您可以询问它是否存在冲突：

SELECT COUNT(*) FROM Table WHERE token REGEXP '$regex'

如果为 2 或更多，则发生冲突，您可以要求用户检查字母并重试。或者也许要求他们输入信息的其他部分，例如姓氏？这将是一个很好的问题，可以把它带给UX人员。

你看过汉明距离吗？

虽然你有字母和数字，但您可以将所有内容转换为二进制(ASCII 值(并使用汉明距离进行比较。如果距离大于某个阈值，请拒绝它。否则，您实际上是在寻找一个字符串指标，以满足您识别"错误识别"字符的需求。你是对的 - 你可能必须自己建造一个。