알고리즘 : 관련 정보를 결정하기 위해 하위 문자열 집계

Question

사용자 하이라이트를 기반으로 텍스트에서 가장 중요한 요소를 얻는 집계 알고리즘을 수행하려고합니다.

당신이 "관련 하이라이트", 1 < = K < = N. (k는 n 개의 문자열입니다)

로 텍스트에서 K 연속 단어를 선택하는 기능이 n 개의 단어를 갖는 텍스트가 상상

k 개의 하이라이트 중 10 ~ 10000 개를 선택한다고 가정하면 가장 중요한 정보를 결정할 수있는 알고리즘이 있습니까?

하이라이트 중 상당 부분이 겹칠 수 있으므로이를 고려해야한다고 생각하십시오. 또한 크롬 확장을위한 것이므로 자바 스크립트에서 솔루션을 찾고있는 것이 바람직합니다.

이것은 클래스 용이 아니며, 군중 기반 요약에 관한 개인 프로젝트 용입니다.

Answer 1

각 사용자가 일부 텍스트를 강조하고 해당 하이라이트가 무엇인지 알고 있다고 가정합니다. 텍스트의 각 단어에 대해 얼마나 많은 사람들이 강조했는지 요약 할 수 있습니다. 당신이 계산할 수있는 한가지는 고정 된 k와 N에 대해 N 개의 단어를 모두 사용하는 k 개의 뻗기의 총합입니다. N 개의 단어가 강조 표시된 횟수의 합이 최대였습니다.

텍스트 내에서 왼쪽에서 오른쪽으로 작업하면서 동적 프로그래밍을 통해이를 수행 할 수 있습니다. 텍스트의 각 지점과 (# 하이라이트, 강조 표시된 총 단어 수, 현재 단어 강조 표시 여부) 가능한 조합은 해당 제약 조건을 충족하는 지점에서 종료되는 최상의 답을 얻기 위해 점수를 계산합니다. 이전 단어에 대한 최상의 답을 사용하여 각 지점에서 가장 좋은 답을 찾을 수 있습니다. 기존의 최상의 답 중 하나를 선택하고 현재 강조 표시를 확장하거나 마지막 단어가 강조 표시된 경우 얻을 수있는 점수를 고려하십시오. 새로운 하이라이트를 시작하십시오. 마지막에는 오른쪽에서 왼쪽으로 전체 텍스트에 대한 최상의 답을 추적합니다.

이렇게하면 강조 표시 할 k 뻗음의 가장 좋은 섹션 형식으로 요약을 제공하며 N 개까지의 단어를 사용하여 가능한 한 많은 단어를 강조 표시합니다. 이 점에 대해 다른 점수 나 다른 강조 표시 제약 조건에 대한 변형이 있다는 것은 의심의 여지가 없습니다. 각 스트레치가 최대 M자인 최적의 k 뻗기 조합을 계산하는 것이 더 쉬울 수도 있습니다.