가장 가까운 일치하는 기존 문자열을 간단한 와일드 카드 문자열로 효율적으로 찾기

Question

나는 식별자 인 문자열 테이블을 가지고 있지만 각 식별자는 고정되어 있거나 일부 정적 조각이있는 변수 식별자 일 수 있습니다. 예를 들어 식별자는 ABC12345이거나 식별자는 DEF**45 일 수 있습니다. *은 임의의 영숫자를 나타냅니다. 이 테이블에는 문자 그대로 수십만 개의 식별자가 있으며 사용자가 입력 한 내용에 따라 입력 된 문자열을 가장 가까운 문자열과 일치 시키려고합니다. 사용자가 ABC12345을 입력하면 직접 일치하므로 모두 설정됩니다. 사용자가 DEF1245을 입력하면 계산이 필요합니다. 나는 Levenshtein 거리가 좋은 후보라고 생각했는데, 그것은이 경우에 가장 가까운이 문자열을 복제하기 위해 두 글자를 변경해야한다고 (이 경우) 알려줄 것이기 때문입니다. 이벤트에 식별자가 DEF12**인데 문제가되지 않을 것입니다. 왜냐하면 둘 다 같은 거리가 될 것이기 때문에 문제가되지는 않을 것입니다.하지만 적어도 두 옵션 모두 유효한 일치라고 알고 있기 때문에 괜찮습니다. 문제는 상당한 효율 문제가있는 데이터베이스에있는 수천 개의 문자열에 대해이 비교를 실행할 수 있다는 것입니다. 제가 선호하는 길이있는 길이는 즉각적인 판별 자이며 같은 거리의 여러 거리는 문제가되지 않습니다. 이 문자열을 처리하는 더 효율적인 방법이 있을까요 아니면 처리를 위해 저장하는 더 좋은 방법일까요? 그것은 거의 반전 정규식처럼 보이지만 어떻게 정규식, 테스트로 각 식별자를 변환하지 않고 그들을 사용할 수있는 이해가 안돼, 그리고 앞으로. 그것은 거리 계산보다 비효율적 인 것처럼 보입니다.

Answer 1

Levenshtein 거리는 두 문장의 문자를 기준으로 계산됩니다. AFAIK는 Levenshtein 거리를 빠르게 할 수있는 사전 계산 단계가 없습니다. 당신은 길이가 고정되어 있기 때문에 이 부분 집합 2, 23, 아이디의 모든 부분 집합을 저장하고, 사용자가 모든 미리 계산 된 부분 집합

• 사용자 유형 2345에 입력 한 내용의 모든 부분 집합을 확인 할 수 있었다, 234, 234, 3, 34, 345, 등 ...
• 이상 부분 집합으로 시작, 입력 한 내용과 사용자와 동일한 부분 집합이있는 모든 ID를 찾을 수 : 정렬 긴 일반적인 susbset
, 23456 12345
• 을 일치합니다

가장 먼저 알지 못하는 것은 얼마나 효율적 일까. 두 번째 (가장 중요한 점은) Levenshtein 거리가 실제로 문제인지 아닌지를 확인해야한다고 생각합니다. 내 경험에 비추어 볼 때 수천 개의 거리 계산으로 검색 속도를 크게 떨어 뜨리지 않아야합니다 (ID가 오래 걸리지 않는 한). 먼저 시도해보십시오. 이후에 최적화를 시도 할 것입니다.