동일한 문자를 사용하여 가장 가까운 문자열을 찾는 알고리즘

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

  •  21-08-2019
  •  | 
  •  

문제

n개의 문자열로 구성된 목록 L과 입력 문자열 S가 주어지면 S에 존재하는 가장 많은 문자를 포함하는 문자열을 L에서 찾는 효율적인 방법은 무엇입니까?우리는 S에 포함된 문자와 가장 밀접하게 구성된 문자열을 L에서 찾고 싶습니다.

확실한 대답은 n개의 문자열을 모두 반복하여 현재 문자열의 문자가 S에 몇 개 있는지 확인하는 것입니다.하지만 이 알고리즘은 자주 실행될 것이며 n 문자열의 목록 L이 데이터베이스에 저장될 것입니다...모든 n 문자열을 수동으로 루프하려면 n*m^2의 big-Oh와 같은 것이 필요합니다. 여기서 n은 L에 있는 문자열 수이고 m은 L에 있는 문자열의 최대 길이이자 S의 최대 길이입니다. ...이 경우 m은 실제로 150의 상수입니다.

단순한 루프보다 더 좋은 방법이 있습니까?빠른 검색 기능을 제공하는 n개의 문자열을 로드할 수 있는 데이터 구조가 있습니까?루프보다 성능이 더 좋은 n개의 문자열 각각에 대해 미리 계산된 메타데이터를 사용하는 알고리즘이 있습니까?

나는 알고리즘에 관심을 갖고 있는 많은 괴짜들이 있다는 것을 알고 있습니다.그러니 도와주세요!

감사해요!

도움이 되었습니까?

해결책

하위 문자열 다음에 오는 경우 트라이 또는 Patrica trie가 좋은 출발점이 될 수 있습니다.

순서가 중요하지 않고 각 기호나 문자의 수만 고려한다면 모든 문자열의 히스토그램을 계산한 다음 입력의 히스토그램과 비교할 것입니다.

               ABCDEFGHIJKLMNOPQRSTUVWXYZ
Hello World => ...11..1...3..2..1....1...

이렇게 하면 비용이 절감됩니다. O(26 * m + n) 대소문자를 구분하지 않는 라틴 문자만 고려하는 경우 전처리를 한 번 더 수행합니다.

m이 상수인 경우 히스토그램을 정규화하여 26차원 단위 구의 26차원 벡터로 해석할 수 있습니다.그럼 당신은 단지 계산할 수 있습니다 내적 두 벡터 사이의 각도의 코사인을 산출하는 두 벡터의 값이며, 이 값은 문자열의 유사성에 비례해야 합니다.

가정 m = 3, 알파벳 A = { 'U', 'V', 'W' } 크기 3만 있고 다음 문자열 목록이 있습니다.

L = { "UUU", "UVW", "WUU" }

히스토그램은 다음과 같습니다.

H = { (3, 0, 0), (1, 1, 1), (2, 0, 1) }

히스토그램 h = (x, y, z) 정규화된다 h' = (x/r, y/r, z/r) ~와 함께 r 히스토그램의 유클리드 표준 h - 그건 r = sqrt(x² + y² + z²).

H' = { (1.000, 0.000, 0.000), (0.577, 0.577, 0.577), (0.894, 0.000, 0.447) }

입력 S = "VVW" 히스토그램이 있습니다 hs = (0, 2, 1) 그리고 정규화된 히스토그램 hs' = (0.000, 0.894, 0.447).

이제 두 히스토그램의 유사성을 계산할 수 있습니다. h1 = (a, b, c) 그리고 h2 = (x, y, z) 두 히스토그램의 유클리드 거리입니다.

d(h1, h2) = sqrt((a - x)² + (b - y)² + (c - z)²)

예를 들어 우리는 얻습니다.

d((3, 0, 0), (0, 2, 1)) = 3.742
d((1, 1, 1), (0, 2, 1)) = 1.414
d((2, 0, 1), (0, 2, 1)) = 2.828

따라서 "UVW"는 "VVW"에 가장 가깝습니다(숫자가 작을수록 유사성이 높음을 나타냄).

정규화된 히스토그램 사용 h1' = (a', b', c') 그리고 h2' = (x', y', z') 두 히스토그램의 내적으로 거리를 계산할 수 있습니다.

d'(h1', h2') = a'x' + b'y' + c'z'

예를 들어 우리는 얻습니다.

d'((1.000, 0.000, 0.000), (0.000, 0.894, 0.447)) = 0.000
d'((0.577, 0.577, 0.577), (0.000, 0.894, 0.447)) = 0.774
d'((0.894, 0.000, 0.447), (0.000, 0.894, 0.447)) = 0.200

이번에도 "UVW"는 "VVW"에 가장 가까운 것으로 결정됩니다(숫자가 클수록 유사성이 높다는 것을 나타냄).

두 버전 모두 서로 다른 숫자를 생성하지만 결과는 항상 동일합니다.예를 들어 맨해튼 거리(L1 표준)와 같은 다른 표준을 사용할 수도 있지만 유한 차원 벡터 공간의 표준은 모두 동일하기 때문에 숫자만 변경됩니다.

다른 팁

당신에게 필요한 것 같네요 트라이.시도는 맞춤법 검사기가 작동하는 방식과 유사한 단어를 검색하는 데 사용됩니다.따라서 문자열 S에 L의 문자열과 동일한 순서로 문자가 있으면 이것이 효과가 있을 수 있습니다.

그러나 스크래블 타일 세트처럼 S의 문자 순서가 관련이 없고 가장 긴 단어를 검색하려는 경우 이는 해결책이 아닙니다.

당신이 원하는 것은 BK-트리.다소 직관적이지 않지만 매우 훌륭합니다. 또한 O(log n) 시간 내에 levenshtein(편집) 거리 임계값 내에서 요소를 검색할 수 있습니다.

입력 문자열의 순서를 지정하려면 그대로 사용하세요.그렇지 않은 경우 개별 문자를 BK-트리에 삽입하기 전에(또는 쿼리하기 전에) 정렬할 수 있습니다.

나는 당신이 찾고 있는 것을 여기에서 찾을 수 있다고 믿습니다: 퍼지 논리 기반 검색 기법

그것은 꽤 무겁지만, 당신이 요구하는 것도 그렇습니다.단어 유사성과 문자 위치 오류에 대해 이야기합니다.

i.e:

L I N E A R T R N A S F O R M
L I N A E R T R A N S F O R M
L E N E A R T R A N S F R M

문제에서 문자의 순서는 중요하지 않은 것 같지만 S라는 단어의 "near-anagrams"를 검색하고 있습니다.

그렇다면 집합 L의 모든 단어를 26개의 정수 배열로 나타낼 수 있습니다(알파벳의 문자가 26개라고 가정).S를 26개의 정수 배열로 유사하게 표현할 수 있습니다.이제 가장 일치하는 항목을 찾으려면 세트 L을 한 번 실행하고 S 벡터와 현재 L 벡터 사이의 거리 측정법을 계산하면 됩니다. 그러나 거리 측정법을 정의하고 싶습니다(예:유클리드/제곱합 또는 맨해튼/절대 차이의 합).벡터의 길이가 일정하므로 이는 O(n) 알고리즘입니다.

다음은 저에게 효과적이며 편집 거리를 제공하는 T-SQL 함수입니다.

예:

  SELECT TOP 1 [StringValue] , edit_distance([StringValue, 'Input Value')
    FROM [SomeTable]
ORDER BY edit_distance([StringValue, 'Input Value')

함수:

CREATE FUNCTION edit_distance(@s1 nvarchar(3999), @s2 nvarchar(3999))
RETURNS int
AS
BEGIN
  DECLARE @s1_len int, @s2_len int, @i int, @j int, @s1_char nchar, @c int, @c_temp int,
    @cv0 varbinary(8000), @cv1 varbinary(8000)
  SELECT @s1_len = LEN(@s1), @s2_len = LEN(@s2), @cv1 = 0x0000, @j = 1, @i = 1, @c = 0
  WHILE @j <= @s2_len
    SELECT @cv1 = @cv1 + CAST(@j AS binary(2)), @j = @j + 1
  WHILE @i <= @s1_len
  BEGIN
    SELECT @s1_char = SUBSTRING(@s1, @i, 1), @c = @i, @cv0 = CAST(@i AS binary(2)), @j = 1
    WHILE @j <= @s2_len
    BEGIN
      SET @c = @c + 1
      SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j-1, 2) AS int) +
        CASE WHEN @s1_char = SUBSTRING(@s2, @j, 1) THEN 0 ELSE 1 END
      IF @c > @c_temp SET @c = @c_temp
      SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j+1, 2) AS int)+1
      IF @c > @c_temp SET @c = @c_temp
      SELECT @cv0 = @cv0 + CAST(@c AS binary(2)), @j = @j + 1
    END
    SELECT @cv1 = @cv0, @i = @i + 1
  END
  RETURN @c
END
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top