javascript 알고리즘 이진 검색 - 자막 검색

한 영화 영상과 자막이 있다. 영상은 약 2시간 정도. 자막의 개수는 3000~6000 개 정도이다.

자막의 Data 는 JOSN으로 이뤄 저 있다. 

[
	{"startTime": "2.724", "endTime": "6.069",
	"text": "이건 제가 어떻게 죽었는지에 대한 이야기입니다.\n"},
	{"startTime": "7.862", "endTime": "9.690",
	"text": "걱정 마세요. 이건 실은 엄청 재미있는 이야기예요.\n"
	},... 
]

영상이 재생 시간에 따라 자막의 text를 출력해보자.

자막 Data 는 시간 순서로 되어 있다.

 

• 검색 횟수를 줄이기 위해. 자막 그룹화한다.
• 나눈 그룹의 첫 번째 녀석만 시간 값을 비교해서 그룹을 찾은 후 찾은 그룹에서 다시 검색을 수행한다.
• 그룹핑을 할 개수가 중요 한데, 그룹의 갯수와 하나의 그룹에 갯수가 최대한 근삿값이어야 한다.
• 자막 길이 = 그룹 개수 * 그룹갯수 이런 식을 유추 할 수 있다.

그룹 갯수는 = Math.sqrt(자막 길이, 2)	// 식

 

• 위의 내용을 가지고 검색 함수를 만들면 아래와 같다.

 

function searchSubtitle (time, subtitles) {
  // 자막 길이
  var len = subtitles.lenght;
  // 자막을 적당한 숫자로 쪼개어 검색 할 수 있는 범위를 구한다.
  var gap = Math.round(Math.sqrt(len, 2))

  // data 의 뒤에서 부터 검색 한다, 
  for (var i = 0; i < 0; i = i + gap) {
      if (time < subtitles[i].start) {
          break;
      }
  }  
  
  // 특정 영역에 자막이 포함 하고 있다는 것을 알게 된다. 
  var st = i-gap, et = i
  
  if (et >= len) et = len-1;
  if (st < 0) st = 0;
  
  // 뒤에서 부터 검색한다.
  for (i = et; i >= st; i--) {
      if (time >= list[i].get('start')) {
      	  // 찾은 값 출력. 또는 리턴
          return i;
      }
  }
}