4

背景

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

问题

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

到目前为止我所做的

我能够根据用户输入检查代码（不区分大小写）并确定它是否完全匹配。如果不是，我会默默地用O's 替换任何 's0并重试。

问题

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

相似字符：

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

3 回答 3

4

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

正如@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;
}
于 2014-08-13T13:23:16.450 回答
2

一种解决方案：将“混淆”字符转换为匹配可能替代字符的正则表达式，然后将扩展的正则表达式与输入匹配。示例：如果输入为“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 人员是一个很好的问题。

于 2014-08-13T03:47:53.647 回答
1

你看过汉明距离了吗？

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

于 2014-08-13T03:34:46.307 回答