표본 크기가 클 때 문자열의 유사성 점수를 효율적으로 계산하는 방법은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/1609742

문제

10,000개의 이메일 주소 목록이 있고 이 목록에서 가장 가까운 "이웃" 중 일부(목록에 있는 다른 이메일 주소와 의심스러울 정도로 가까운 이메일 주소로 정의됨)를 찾고 싶다고 가정해 보겠습니다.

계산하는 방법을 알고 있어요. 레벤슈타인 거리 두 문자열 사이 (덕분에 이 질문), 이를 통해 한 문자열을 다른 문자열로 변환하는 데 필요한 작업 수에 대한 점수를 얻을 수 있습니다.

Levenshtein 점수가 N보다 작은 두 개의 문자열로 "의심스럽게 다른 이메일 주소와 가까운"을 정의한다고 가정해 보겠습니다.

가능한 모든 문자열을 목록의 다른 모든 가능한 문자열과 비교하는 것 외에 점수가 이 임계값보다 낮은 문자열 쌍을 찾는 더 효율적인 방법이 있습니까?즉, 이런 유형의 문제를 다른 것보다 더 빨리 해결할 수 있습니까? O(n^2)?

Levenshtein 점수는 이 문제에 대한 알고리즘 선택이 좋지 않습니까?

도움이 되었습니까?

해결책

YUP- 당신은 a를 사용하여 O (log n) 시간의 주어진 거리 내에서 모든 문자열을 찾을 수 있습니다. BK-Tree. 거리 n이있는 모든 스트링을 생성하는 대체 솔루션은 1의 Levenshtein 거리에 대해 더 빠를 수 있지만, 작업량은 더 먼 거리에 대한 통제 불완전한 풍선을 빠르게 제어 할 수 없습니다.

다른 팁

Levenshtein으로 할 수 있습니다 O(kl), 어디 k 최대 거리이고 L은 최대 문자열입니다.

기본적으로 기본 Levenshtein을 계산하는 방법을 알면 모든 결과가 k 주요 대각선에서는보다 커야합니다 k. 따라서 주 대각선을 너비로 계산하는 경우 2k + 1 충분할 것입니다.

10000 개의 이메일 주소가있는 경우 더 빠른 알고리즘이 필요하지 않습니다. 컴퓨터는 계산할 수 있습니다 O(N^2) 충분히 빠릅니다.

Levenshtein은 이런 종류의 문제에 매우 좋습니다.

또한 고려할 수있는 것은 비교하기 전에 Soundex로 이메일을 변환하는 것입니다. 당신은 아마 더 나은 결과를 얻을 것입니다.

이 문제는 다음과 같이 알려져 있습니다. 클러스터링 그리고 더 큰 것의 일부입니다 중복 제거 문제(클러스터의 어떤 구성원이 "올바른" 구성원인지 결정하는 문제) 병합 제거.

나는 정확히 이 주제에 관한 몇 가지 연구 논문을 읽은 적이 있습니다(이름은 아래에 있음). 기본적으로 저자는 다음을 사용했습니다. 제한된 크기의 슬라이딩 윈도우 정렬된 문자열 목록에 대해그들은 단지 비교할 것입니다( 거리 편집 알고리즘) N*N 문자열 내부에 창을 사용하여 계산 복잡도를 줄입니다.두 문자열이 유사해 보이면 문자열로 결합되었습니다. 무리 (별도의 클러스터 테이블에 레코드를 삽입하여)

목록의 첫 번째 전달은 다음과 같습니다. 두 번째 패스 끈은 어디에 있었나 반전 정리되기 전에.이렇게 하면 문자열이 다른 머리 같은 창의 일부로 평가될 만큼 가까이 다가갈 수 있는 또 다른 기회가 있었습니다.이 두 번째 패스에서 문자열이 창에 있는 두 개 이상의 문자열과 충분히 가까워 보이고 해당 문자열이 이미 자체 클러스터(첫 번째 패스에서 발견됨)의 일부인 경우 두 클러스터는 다음과 같습니다. 병합된 (클러스터 테이블을 업데이트하여) 현재 문자열이 새로 병합된 클러스터에 추가됩니다.이러한 클러스터링 접근 방식은 다음과 같이 알려져 있습니다. 조합 찾기 연산.

그런 다음 창을 상위 ​​X 목록으로 대체하여 알고리즘을 개선했습니다. 상당히 독특한 프로토타입.각각의 새로운 문자열은 상위 X개의 프로토타입 각각과 비교됩니다.문자열이 프로토타입 중 하나와 충분히 가까워 보이면 문자열이 프로토타입에 추가됩니다. 프로토타입 클러스터.어떤 프로토타입도 충분히 유사해 보이지 않는다면 문자열은 새로운 프로토타입이 될 것입니다. 가장 오래된 프로토타입을 밀어내는 것 상위 X 목록 중(프로토타입 클러스터의 어떤 문자열을 전체 클러스터를 나타내는 새 프로토타입으로 사용해야 하는지 결정하기 위해 경험적 논리가 사용되었습니다.)다시 말하지만, 문자열이 여러 프로토타입과 유사해 보인다면 모든 클러스터가 병합됩니다.

나는 한때 목록 크기가 약 1천만~5천만 개의 레코드인 이름/주소 레코드의 중복 제거를 위해 이 알고리즘을 구현한 적이 있으며 매우 빠르게 작동했습니다(중복도 잘 발견되었습니다).

이러한 문제에 대해 전반적으로 가장 까다로운 부분은 올바른 값을 찾는 것입니다. 유사성 임계값.아이디어는 너무 많이 생산하지 않고 모든 중복을 포착하는 것입니다. 거짓 긍정.특성이 서로 다른 데이터에는 서로 다른 임계값이 필요한 경향이 있습니다.일부 알고리즘은 OCR 오류에 더 좋고, 다른 알고리즘은 오타에 더 좋고, 다른 알고리즘은 음성 오류(예: 전화로 이름을 알릴 때)에 더 좋기 때문에 편집 거리 알고리즘의 선택도 중요합니다.

클러스터링 알고리즘이 구현되면 이를 테스트하는 좋은 방법은 고유한 샘플 목록을 얻는 것입니다. 각 샘플을 인위적으로 돌연변이시키다 모든 변형이 동일한 상위에서 나왔다는 사실을 유지하면서 변형을 생성합니다.그런 다음 이 목록을 섞어 알고리즘에 입력합니다.원본 클러스터링과 중복 제거 알고리즘에 의해 생성된 클러스터링을 비교하면 다음과 같은 결과를 얻을 수 있습니다. 효율성 점수.

서지:

에르난데스 M.1995년, 대규모 데이터베이스의 병합/제거 문제.

몬지 A.1997년, 대략적인 중복 데이터베이스 레코드를 검색하기 위한 효율적인 도메인 독립적 알고리즘.

나는 당신이 O (n^2)보다 더 잘할 수 있다고 생각하지 않지만 애플리케이션을 사용할 수있게하기에 충분한 속도가있을 수있는 작은 최적화를 할 수 있습니다.

  • 먼저 @ 이후에 모든 이메일 주소를 정렬 할 수 있으며 그 주소 만 비교할 수 있습니다.
  • N보다 커지면 두 주소 사이의 거리를 계산하지 않을 수 있습니다.

편집 : 실제로 O (n^2)보다 더 잘할 수 있습니다. 아래의 Nick Johnsons 답변을보십시오.

10,000 개의 이메일 주소가 너무 많지 않습니다. 더 큰 공간에서 유사성 검색을 위해 사용할 수 있습니다. 대안 그리고 최소 경쟁. 이 알고리즘은 구현하기가 조금 더 복잡하지만 넓은 공간에서는 훨씬 더 효율적입니다.

문제를 뒤집는 조건에서 더 잘할 수 있습니다.

여기서 10.000 주소가 '고정'되었다고 생각합니다. 그렇지 않으면 업데이트 메커니즘을 추가해야합니다.

아이디어는 Levenshtein 거리를 사용하는 것입니다. 그러나 Python에서 'Reverse'모드에서 :

class Addresses:
  def __init__(self,addresses):
    self.rep = dict()
    self.rep[0] = self.generate_base(addresses)
      # simple dictionary which associate an address to itself

    self.rep[1] = self.generate_level(1)
    self.rep[2] = self.generate_level(2)
    # Until N

그만큼 generate_level 메소드는 이전 수준에서 이미 존재하는 변형을 빼고 이전 세트에서 가능한 모든 변형을 생성합니다. 키와 관련된 값으로 '원점'을 보존합니다.

그런 다음 다양한 세트에서 단어를 조회하면됩니다.

  def getAddress(self, address):
    list = self.rep.keys()
    list.sort()
    for index in list:
      if address in self.rep[index]:
        return (index, self.rep[index][address]) # Tuple (distance, origin)
    return None

그렇게하면 다양한 세트를 한 번 계산합니다 (일부 시간이 걸리지 만 ...이를 직렬화하고 영원히 유지할 수 있습니다).

그런 다음 조회는 O (n^2)보다 훨씬 효율적이지만 생성 된 세트의 크기에 따라 달라지기 때문에 정확히 어렵습니다.

참조를 위해 다음을 살펴보십시오. http://norvig.com/spell-correct.html

3 개의 문자열이 있다고 가정 해 봅시다.

1- "ABC"2- "BCD"3- "CDE"

1과 2 사이의 L 거리는 2입니다 ( 'a', 추가 'd'). 2와 3 사이의 L 거리는 2입니다 ( 'b', 추가 'e').

귀하의 질문은 위의 2 가지 비교를 사용하여 1과 3 사이의 L 거리를 추론 할 수 있는지 여부입니다. 내 대답은 아니오 야.

1과 3 사이의 L 거리는 3 (모든 문자 교체)이므로 처음 두 계산의 점수로 인해 추론 할 수있는 방법이 없습니다. 점수는 결실, 삽입 또는 대체 작업이 수행되었는지 여부를 밝히지 않습니다.

그래서 Levenshtein은 큰 목록을위한 불쌍한 선택이라고 말하고 싶습니다.

실제로 이메일 주소를 비교하는 경우이를 수행하는 명백한 방법 중 하나는 Levenshtein 알고리즘을 도메인 매핑과 결합하는 것입니다. 동일한 도메인을 사용하여 여러 번 가입했을 때를 생각할 수 있지만 이메일 주소의 사용자 이름 부분에 대한 변형을 생각할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top