2 세트 사이의 모든 문자열 쌍을 모두 찾아서 첫 번째 문자열의 모든 단어가 모두 2 번째 문자열에 포함되도록합니다.

cs.stackexchange https://cs.stackexchange.com/questions/120658

  •  29-09-2020
  •  | 
  •  

문제

2 개의 큰 문자열 세트가 있습니다 (실제로 제품 이름은 제품 이름입니다). "큰"은 몇 백만 개의 문자열을 의미합니다.

예 :

1 : 

Some good product
Another product
Some name
Blah
.

2 : 

Very long some product name with words blah
Another very long product name
asd asd sad sad asdsa
Blah blah blah
.

1을 설정하면 "좋은"이름이 들어 있습니다. 2 세트에는 "더티"이름이 포함되어 있습니다.

원하는 위치 : 세트 2의 모든 항목에 대해 (추가 : Item2) Item1의 모든 단어가 Item2 에 포함되어 있도록 설정 1 (추가 : Item1)에서 가장 긴 항목을 찾습니다. 주어진 예의 경우 쌍은 다음과 같습니다. 

Very long SOME product NAME with words blah => Some name
ANOTHER very long PRODUCT name              => Another product
asd asd sad sad asdsa                       => none
BLAH blah blah                              => blah
.

지금까지 나는 무차별의 힘 알고리즘보다 더 좋은 것을 생각할 수 없었다 :

  1. SET 1의 모든 문자열을 단어= 단어 목록으로 나열하고 3
    2. 를 설정하십시오.
  2. SET 2의 모든 문자열을 단어= 단어 목록을 가져오고 4
    3. 를 설정하십시오.
  3. 세트 3에서 워드 목록을 선택합니다. (추가 : List3), List3에 완전히 포함 된 일부 목록을 찾을 때까지 세트 4의 모든 단어 목록과 비교합니다.

    4. 그러나 그것은 매우 높은 복잡성을 가지고 있으며 매우 느리게 작동합니다. 나의 간단한 구현은 1 쌍을 찾기 위해 약 1.8s를 소비합니다. MySQL-FullText 인덱스를 사용하여 동일한 작업을 구현하면 1 개의 모든 단어가 포함 된 문자열을 검색 할 수 있음) 1 검색은 약 0.4s가 걸립니다. 그래서 나는 작은 혈액으로 여기에 적용될 수있는 좋은 접근 방식이 있는지 궁금합니다.)

    내 프로그래밍 언어는 PHP7입니다. 데이터는 MySQL DB에 저장됩니다.

도움이 되었습니까?

해결책

는 실제로 실제로 효과적 일 수있는 두 가지 가능한 접근 방식을 열거하지만 최악의 실행 시간이 목록에있는 것보다 낫지 만

인덱스

각 단어에 대한 색인을 빌드 할 수 있습니다. 해시 테이블을 만듭니다. 어떤 깨끗한 이름에 나타나는 각 단어에 대해 해시 테이블은 그 단어가 해당 단어가 포함 된 모든 더러운 이름 목록에 해당 단어를 맵핑합니다. 이 해시 테이블은 더러운 이름 (SET2) 세트의 선형 스캔에서 한 번 구축 될 수 있습니다.

그런 다음 깨끗한 이름을 고려할 때 깨끗한 이름으로 단어를 반복합니다. 각 단어에 대해 해시 테이블에서 찾아서 해당 단어가 포함 된 모든 더러운 이름을 반복하고 깨끗한 이름과 공통된 단어 수를 확인하십시오. 최상의 일치를 유지하십시오.

이것은 조금 최적화 될 수 있습니다. 깨끗한 이름에 많은 더러운 이름에서 발생하는 단어가 포함되어 있으면 그 단어가 느리게됩니다. 따라서 각 단어가 더러운 이름 (그 빈도)에서 발생하고 해시 테이블에 저장할 횟수를 찾을 수 있습니다. 그런 다음 깨끗한 이름이 주어지면 빈도가 증가하는 순서로 깨끗한 이름으로 단어를 반복하여 지금까지 발견 한 가장 좋은 일치를 추적합니다. $ \ ell $ 의 일치 항목을 발견 한 경우 $ \를 반복하지 않고 일찍 반복을 중지 할 수 있습니다. ell-1 $ 유효한 일치 항목이 없어지 않고 깨끗한 이름에서 가장 높은 빈도 단어.

은 시도

이름의 단어의 순서는 부적합하므로 각 구절의 단어를 정렬하십시오. 예를 들어 '좋은 제품'이 '좋은 제품'이됩니다. 각 세트의 각 이름 으로이 작업을 수행하십시오.

다음에 좋은 이름 집합을 나타내는 TRIE를 작성하십시오 (SET1). 예를 들어, 예제에서 TRIE는 

+-- another --+-- product --+
|`-- blah --+
|`-- good --+-- product --+-- some --+
 `-- name --+-- some --+
.

이제 더러운 이름을 선택하십시오. 우리는 트리에서 일치하는 것을 찾고 싶습니다. 재귀 알고리즘을 사용하여 모든 일치 항목을 찾으려면 모든 일치 항목을 찾으려면 Trie $ T $ , $ T $ 라고 표시된 $ W_1 $ 이므로 해당 에지가 가리키는 하위 트리에서 $ W_2 \ CDOTS W_N $ 에 대한 모든 일치 항목을 재귀 적으로 찾습니다. 또한 $ W_2 \ CDOTS 수학 컨테이너 "> $ T $ 에서 $ 에 대한 모든 일치를 재귀 적으로 찾습니다. 일단 모든 일치를 찾았 으면 가장 긴 것을 유지하십시오.

예를 들어 '매우 긴 제품 이름'의 경우,이를 분류 한 후 '또 다른 긴 이름 제품이 매우'됩니다. Subtrie +-- product --+에서 'Long Name Product Unery'에 대한 모든 일치를 재귀 적으로 찾아서 주 Trie에서 'Long Name Product Unery'에 대한 모든 일치 항목을 찾아서 Trie를 찾습니다.

이 검색 프로세스는 다양한 방식으로 최적화 될 수 있습니다. 예를 들어, 지금까지 가장 긴 경기를 추적하고 재귀 호출이 당신이 일치하는 단어 수를 기반으로 얼마나 많은 단어를 기반으로 더 긴 경기를 찾을 수 있는지 여부를 일찍 발견하면 일찍 일찍 멈추는 경우 멀리 그리고 얼마나 많은 단어가 남아 있습니다.

조직식 순서로 정렬 할 필요가 없습니다. 일관성있는 한 다른 순서로 정렬 할 수 있습니다. 예를 들어 전체 데이터 집합의 단어 빈도로 정렬 할 수 있습니다 (최소한의 단어가 가장 적은 단어로). 이는 재귀 호출 수를 줄일 수 있습니다.

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