부분 문자열 일치 길이를 기준으로 효율적인 SQL 버킷 정렬

Question

문자열이 알파벳순으로 인덱싱 된 SQL 데이터베이스 테이블에서 부분 문자열 일치를 기준으로 검색 쿼리를 수행하려면 어떻게해야합니까? 우리는 단지의 길이에 관심

bandana (index 0-3 matched) 
banana (index 0-2 matched) 
banker 
bad  (index 0-1 matched) 
bed  (index 0 matched) 
brother 

참고를 다음과 같이 주문한 결과를 기대

bad 
banana 
bandana 
banker 
bed 
brother 

그리고 검색 문자열 band : 데이터 세트 주어진 예를 들어

, substring matched. 각 물통 에 속하는 일치 항목을 사전 순으로 정렬 할 필요는 없으며 단지에 속하는 버킷에만 관심이 있습니다. 주문 경기 길이

에 따라 적절한 통에 각 행을 두는 각 행

내 입력에 대한 문자열 일치의 길이를보고

1. :

   그래서 나는 문제가 포함 순진하게 생각 버킷을 내림차순으로 정렬합니다. (일치하는 4 개의 문자, 3 개의 일치하는 문자, 2 ..)

그러나 이것은 비싸다고 들지만, SQL 또는 C# 훌륭하게?

여기에서 얻을 수있는 비슷한 문제/패턴이 있습니까?

많은 감사

Answer 1

문자열 연산과 sql-server는 afaik와 가장 일치하지 않습니다.

최선의 방법은 Bayer-Moore-horspool 수정 버전을 사용하여 일치하는 문자 수를 찾는 것입니다. 그러나, 놓치기 만하면 전체 단어 길이는 건너 뛰지 않고 최대 일치 길이 만 건너 뜁니다. 그런 다음 복잡한 버켓에 삽입하기 만하면됩니다.

Answer 2

가장 효율적인 방법인지는 확실하지 않지만.

숫자 표를 사용하여 문자열을 문자로 분할하고이를 검색 문자열의 분할로 결합한 다음 계수 및 문자열로 정렬하십시오.

DECLARE @t TABLE (string VARCHAR(50)) 

INSERT INTO @t (string) 
VALUES 
    ('bad'), 
    ('banana'), 
    ('bandana'), 
    ('banker'), 
    ('bed'), 
    ('brother') 

DECLARE @search VARCHAR(50) = 'band' 

;WITH numbers AS 
(
    SELECT TOP 10000 ROW_NUMBER() OVER(ORDER BY t1.number) AS n 
    FROM master..spt_values t1 
    CROSS JOIN master..spt_values t2 
) 
SELECT string 
FROM @t t 
CROSS APPLY (
    SELECT SUBSTRING(t.string, numbers.n, 1) c, n 
    FROM numbers 
    WHERE numbers.n <= LEN(string) 
) s1 
JOIN (
    SELECT SUBSTRING(@search, numbers.n, 1) c, n 
    FROM numbers 
    WHERE numbers.n <= LEN(@search) 
) s2 ON s2.c = s1.c 
    AND s2.n = s1.n 
GROUP BY string 
ORDER BY COUNT(1) DESC, string 

demo