Auto Completion, and Fuzzy Search

# Auto Completion, and Fuzzy Search Category 자동완성 및 제목의 일부분만을 이용해서 reco/article 찾기 등을 위해 만들고 있는 중. 우선 테스트 먼저 해보고 싶으신 분들은 G (Go) 키를 누르시거나 오른쪽 위의 Fuzzy search 버튼을 눌러서 이것저것 검색어 넣고 경험해 보시길. 아니면 Recoeve.net (/user/kipid?cat=[Music/Break]--K-pop) 가셔서 Fuzzy search (검색: Go) 버튼이나 ToR (목록: Tables of Recos) 버튼 누르셔서 경험해 보셔도 좋을듯. 내가 힌트를 얻은 곳은 sublime text 이고, 어딘가에 공개된 code 도 있을것 같지만 베끼기도 귀찮고 내가 쓰는 용도에 최적화 하기도 힘들것 같아서 직접 짜보기로 결심. 뭐 크게 어려울거 같지는 않고, 짜는 과정에서 배우는 것도 많을거 같아서... Google 에서 "Fuzzy search", "Approximate string matching" , "Fuzzy search sublime text" 등을 간단히 검색해보긴 했는데, 딱히 구체적인 방법론이나 code 를 posting 해준데는 없는거 같음. 한글 초성검색과도 관련 있긴 함. 내 코드는 초중종성 따지지 않고 들어가 있기만 하다면 모음이든 자음이든 검색해주긴 하지만...

Recoeve.net 에 구현한 Fuzzy search 예제.

## TOC ##[.no-sec-N#sec-Progress] Progress 우선 기본적인 구현은 https://kipid.tistory.com/entry/Lists 에서 해놨는데.... 앞으로 고치고 싶은것들 리스트 좀 여기다가 정리해 놓으면서 업데이트 해야겠음. ### To do

• Sorting by DESC MMS 를 insertion sort 로 했는데, 이거 더 빠른 sort 로 바꾸긴 해야할듯? (뭐 정렬해야하는 갯수가 그리 많은건 아니라서 이정도면 충분할거 같기도 하지만...)

### Done

• 마우스로 복붙할때도 제대로 동작하도록 만들자. : on "input keyup cut paste" with clearTimeout/setTimeout 으로 해결했음. 그냥 on "input" 만으로 되는건데, IE 에서까지 제대로 동작하게 하느라 좀 복잡해짐 ㅡㅡ. 그지같은 IE.
• m.fsResult 만 저장해놓고 m.fsFullList 가지고 fuzzy search 하는 식인데... 이게 fsFullList 를 바꾸고 싶을때도 있을테니, m.fuzzySearch(pattern, subList) 돌아가는 방식을 조금 더 일반화 해놓을 필요가 있을듯.

## How to operate? Category 입력할 때, sublime text 자동 완성처럼 pmp 입력하면 "[Physics/Math]--Physics" 같은 리스트들이 떠서 선택 되도록 만들기. 언어는 javascript 이용. ## Match score ### From the distance between match start and end Python 에서 Sublime text fuzzy search 같은걸 만들어봤다고 posting 한 글 에서 쓴 방식인데, match score 매기는게 뭔가 부족해보임. 거기서는 \text{score} =\frac{100} {(1+\text{match.start()}) (\text{match.end()}-\text{match.start()}+1)} 와 같이 첫번째 match (=match.start()) 가 string 초반에 있을수록 점수가 높고, match 된 전체 길이 (=match.end()-match.start()+1) 가 짧을수록 점수가 높도록 설계됨. 내가 원하는 설계 및 결과를 주는게 아닐듯 함. (난 꽤나 긴 string 에서 match 를 찾기 때문에...) ### From the distances among the contiguous matches 우선 match 시켜볼 string list 들이 있을테고, 찾아야 하는 pattern 을 입력받음. 우선 한개의 string $S$ 를 다음과 같은 single letter/character list (n개의 char) 로 풀어서 보고 S = s_1 s_2 s_3 \cdots s_n pattern $P$ 도 다음과 같이 single letter/character list (m개의 char) 로 풀어서 보자. P = p_1 p_2 \cdots p_m

한글의 경우 "각" 은 "ㄱㅏㄱ" 과 같이 풀어서 생각. (한글과 비슷하게 풀어서 생각할 수 있는 언어들이 또 있나? 일본어랑 중국어???) 영어 "ABC" 는 이미 풀어져 있음. 단 영어와 같은 latin 계열 언어는 ignore case 옵션이 붙을 수 있음.

String $S$ 안에 pattern $P$ 에 해당하는 letter 들이 match 되어야 하고, match score 는 인접한 match 간 간격이 좁을수록 높아지는 형태로 디자인하자. $P$ 를 $S$ 에 match 시켰을 때의 각 pattern 의 match 위치를 $m_1$, $m_2$, $m_3$, $\cdots$, $m_m$ 이라고 하자. 이 때의 match score candidate $C_0$ 를 다음과 같이 정해보자. (이걸 잘 디자인해야 원하는 match ordering 을 얻을 수 있다.) C_0 = \sum_{i=2}^{m} g (m_{i-1}, m_i) where g (m_1, m_2) = \left\{ \begin{array}{ll} 8 \times (5 - | m_2 - m_1 |) & \text{when } | m_2 - m_1 | < 5 \\ 0 & \text{when } | m_2 - m_1 | \geq 5 \\ \end{array} \right. 굳이 5개 차이를 제한으로 둔건 한글 초성검색을 염두해 둔 것임. 한글의 경우 초성검색을 사용할 경우도 있을텐데, "김밥" 을 찾으려고 "ㄱㅂ" 를 친다고 했을때 요런거에도 점수를 좀 높이고자 함이 있어서임. "김밥" 은 "ㄱㅣㅁㅂㅏㅂ" 으로 풀어쓴 다음 검색을 할텐데, "ㄱ" 과 "ㅂ" 은 어느정도 떨어지기 때문에 한글자정도 떨어진거에는 두글자 이상 떨어진 것보다 더 점수를 부여하게 됨. (뭐 5~7 정도가 생각났는데 대충 5로 잡아보고, 결과가 맘에 안들면 tuning 해야 할듯.) ### Other options? 식 에서 8을 곱한건 나중에 다른 방식으로 match score 를 약간 변경/변형할 경우를 염두에 둔 것. 예를 들어

• 첫 match 위치가 string 처음에 더 가까울수록 점수를 더 주자.
• Case-sensitive match 의 경우 점수를 더 주자. (영어의 경우)
• 개인적으로는 자동 한영변환 match 도 구현해놨는데, 한영-sensitive match 의 경우 점수를 더 주는 것도 생각해볼 수 있음.
• Word 첫번째에 match 될 경우 점수를 더 주자. ("[Physics/Math]--Physics" 같은걸 찾고자 할 때, "pmp" 식으로 많이 칠테니까. "hah" 가 아니라.)
• 한글의 경우 초성에 match 되었을 경우에 점수를 더 주자. (보통 종성 이용해서 검색하지는 않을테니까.)

와 같은 것들을 추가할수도 있을테니까. 두 점수의 비중을 잘 조절해야 원하는 결과가 나올텐데, match score 의 datatype 으로 integer 를 쓰는 이상 점수의 세분화를 위해서는 scale 을 적당히 키울 필요가 있음. 이 option 들 중에서도 가장 간단하고, 구현이 쉽고, 효용이 좋을거 같은것만 선택해서 match score candidate $C_1$ 을 다음과 같이 정해보자. C_1 = \sum_{i=2}^{m} g (m_{i-1}, m_i) + \sum_{i=1}^{m} f (S, m_i, P, i) where $g$ is from and $f$ is f (S, m_i, P, i) = \left\{ \begin{array}{ll} 8 & \text{when } s_{m_i} = p_i \\ 0 & \text{when } s_{m_i} \neq p_i \\ \end{array} \right. with case-insensitive equality. ## Maximum match score Match score 에서 주의할 점은 pattern $P$ 를 string $S$ 에 match 시키는 방법이 한가지가 아닐 수 있다는 점이다. 예를 들면 pattern "star" 를 string "sssssttttttaaaaarrrrrrrrstar" 에 match 시킨다고 했을때, "{s}ssss{t}ttttt{a}aaaa{r}rrrrrrrstar", "sss{s}sttttt{t}a{a}aaarrrrrr{r}rstar", "sssssttttttaaaaarrrrrrrr{s}{t}{a}{r}" 등 여러 형태로 match 시킬 수 있게 된다. 이 때에는 가장 match score 가 큰 것을 기준으로 삼자. 앞 얘제에서는 모든 letter 가 붙어있는 "sssssttttttaaaaarrrrrrrr{s}{t}{a}{r}" 가 될 것이다. 이 과정을 잘 알고리즘화 해놔야 빠르게 검색이 가능할텐데, 어떻게 해야할까???

1. 우선 string $S$ 에 pattern $P$ 가 모두 들어 있는지 확인. 이 과정은 우선 $S$ 를 첫부분부터 scanning 하면서 $p_1$ 이 있는지 확인하고, 그 이후위치부터 $p_2$ 가 있는지 확인, 다시 그 이후부터 $p_3$ 이 있는지 확인하는 식으로 모든 $p_i$ 를 확인하는 식으로 이루어진다.
2. match 위치들 $m_1, m_2, \cdots, m_m$ 들이 저장되어 있을텐데, 이건 첫 match 들 위치일테니 $m_m$ 위치 이후에 $p_m$ match 가 있는지 확인하고 이때의 match score 가 이전 max match score 값보다 큰지 확인하는 식으로 비교. (Match 사이의 distance 로만 match score 가 결정된다면 $m-1$ 부터 sub-routine 을 시작해도 됨. $m_m$ 을 더 키워봤자 이전보다 낮은 match score 가 나올게 뻔하니까.)
3. $m_m$ 이후 $p_m$ match 가 더이상 찾아지지 않는다면, $m_{m-1}$ 위치를 하나 증가시키면서 pattern $p_{m-1}p_{m}$ 을 찾고 이떄의 match score 를 이전의 max match score 와 비교. Sub-routine 으로 바뀐 $m_m$ 이후의 $p_m$ 도 또다시 돌려봐야 함.
4. 같은 방식으로 $m_1$ 을 하나 증가시켜서 $p_1 p_2 \cdots p_m$ 을 찾고, sub-routine 까지 다 돌려보면서 max match score 를 찾고 그때의 $m_1, m_2, \cdots, m_m$ 를 기억해 놓으면 됨. findNextMatchFromIndices 로 match 가 없을때까지 계속 찾으면 되는듯. (재귀함수 쓰는게 아닌듯.)

이러면 모든 pattern match 에 대한 match score 비교가 이루어진 것이기 때문에 max match score 를 찾았다고 확신할 수 있음. 과정이 많아서 ($O(n^2)$?) 시간이 꽤 오래걸릴거라고 생각되기도 하지만, 대부분의 경우 pattern match 의 갯수가 그렇게 크지는 않을거기 때문에 감당해 낼 수 있는 시간안에 대부분 처리를 끝낼수는 있을듯? 뭐 이건 실제 code 구현하고 테스트 해보면서 느껴야 할듯.

굳이 모든 가능한 match 들을 찾고 그때의 match score 를 다 비교하면서 maximum match score 를 찾을 필요는 없을거 같기도... 그냥 적당히 비교하고 "대충의 maximum match score 는 이정도 값이다."란 것만 뽑아내고 보여줘도 이게 사용자 입장에서 심하게 거슬리지만 않는다면, 굳이 느리게 동작할거 없이 빠르게 대충의 결과를 알려주는게 사용자 경험에는 더 좋을것도 같음. 즉, $m-1$ 부터 sub-routine 을 시작해서 시간을 조금이라도 줄여봅시다? (어느정도에서 협상을 해야할지 헷갈리네. 엄청 느렸던건 뭐 때문이었을까나?)

## Open source ### 기본 variables ```[.linenums.scrollable] $window=$(window); $out_focus=$("#out-focus"); $fuzzy_search_container=$("#fuzzy-search-container"); $fuzzy_search=$("#fuzzy-search"); $fuzzy_search_list=$("#fuzzy-search-list"); ```/ ### 한글의 초성/중성/종성 구분 및 한영/영한 자동변환 한글의 초성/중성/종성을 구분 및 한영/영한 자동변환해서도 동작하게 만들려고 만든 mapping. ```[.linenums.scrollable] //////////////////////////////////////////////////// // Hangul (Korean) split and map to English // KE : Korean Expanded //////////////////////////////////////////////////// m.jamoKE = ["ㄱ", "ㄱㄱ", "ㄱㅅ", "ㄴ", "ㄴㅈ", "ㄴㅎ", "ㄷ", "ㄷㄷ", "ㄹ", "ㄹㄱ", "ㄹㅁ", "ㄹㅂ", "ㄹㅅ", "ㄹㅌ", "ㄹㅍ", "ㄹㅎ", "ㅁ", "ㅂ", "ㅂㅂ", "ㅂㅅ", "ㅅ", "ㅅㅅ", "ㅇ", "ㅈ", "ㅈㅈ", "ㅊ", "ㅋ", "ㅌ", "ㅍ", "ㅎ", "ㅏ", "ㅐ", "ㅑ", "ㅒ", "ㅓ", "ㅔ", "ㅕ", "ㅖ", "ㅗ", "ㅗㅏ", "ㅗㅐ", "ㅗㅣ", "ㅛ", "ㅜ", "ㅜㅓ", "ㅜㅔ", "ㅜㅣ", "ㅠ", "ㅡ", "ㅡㅣ", "ㅣ"]; m.jamo = ["ㄱ", "ㄲ", "ㄳ", "ㄴ", "ㄵ", "ㄶ", "ㄷ", "ㄸ", "ㄹ", "ㄺ", "ㄻ", "ㄼ", "ㄽ", "ㄾ", "ㄿ", "ㅀ", "ㅁ", "ㅂ", "ㅃ", "ㅄ", "ㅅ", "ㅆ", "ㅇ", "ㅈ", "ㅉ", "ㅊ", "ㅋ", "ㅌ", "ㅍ", "ㅎ", "ㅏ", "ㅐ", "ㅑ", "ㅒ", "ㅓ", "ㅔ", "ㅕ", "ㅖ", "ㅗ", "ㅘ", "ㅙ", "ㅚ", "ㅛ", "ㅜ", "ㅝ", "ㅞ", "ㅟ", "ㅠ", "ㅡ", "ㅢ", "ㅣ"]; m.mapKE = {"q":"ㅂ", "Q":"ㅃ", "w":"ㅈ", "W":"ㅉ", "e":"ㄷ", "E":"ㄸ", "r":"ㄱ", "R":"ㄲ", "t":"ㅅ", "T":"ㅆ", "y":"ㅛ", "Y":"ㅛ", "u":"ㅕ", "U":"ㅕ", "i":"ㅑ", "I":"ㅑ", "o":"ㅐ", "O":"ㅒ", "p":"ㅔ", "P":"ㅖ", "a":"ㅁ", "A":"ㅁ", "s":"ㄴ", "S":"ㄴ", "d":"ㅇ", "D":"ㅇ", "f":"ㄹ", "F":"ㄹ", "g":"ㅎ", "G":"ㅎ", "h":"ㅗ", "H":"ㅗ", "j":"ㅓ", "J":"ㅓ", "k":"ㅏ", "K":"ㅏ", "l":"ㅣ", "L":"ㅣ", "z":"ㅋ", "Z":"ㅋ", "x":"ㅌ", "X":"ㅌ", "c":"ㅊ", "C":"ㅊ", "v":"ㅍ", "V":"ㅍ", "b":"ㅠ", "B":"ㅠ", "n":"ㅜ", "N":"ㅜ", "m":"ㅡ", "M":"ㅡ"}; for (let p in m.mapKE) { m.mapKE[m.mapKE[p]]=p; } m.rChoKE = ["ㄱ", "ㄱㄱ", "ㄴ", "ㄷ", "ㄷㄷ", "ㄹ", "ㅁ", "ㅂ", "ㅂㅂ", "ㅅ", "ㅅㅅ", "ㅇ", "ㅈ", "ㅈㅈ", "ㅊ", "ㅋ", "ㅌ", "ㅍ", "ㅎ"]; m.rCho = ["ㄱ", "ㄲ", "ㄴ", "ㄷ", "ㄸ", "ㄹ", "ㅁ", "ㅂ", "ㅃ", "ㅅ", "ㅆ", "ㅇ", "ㅈ", "ㅉ", "ㅊ", "ㅋ", "ㅌ", "ㅍ", "ㅎ"]; m.rJungKE = ["ㅏ", "ㅐ", "ㅑ", "ㅒ", "ㅓ", "ㅔ", "ㅕ", "ㅖ", "ㅗ", "ㅗㅏ", "ㅗㅐ", "ㅗㅣ", "ㅛ", "ㅜ", "ㅜㅓ", "ㅜㅔ", "ㅜㅣ", "ㅠ", "ㅡ", "ㅡㅣ", "ㅣ"]; m.rJung = ["ㅏ", "ㅐ", "ㅑ", "ㅒ", "ㅓ", "ㅔ", "ㅕ", "ㅖ", "ㅗ", "ㅘ", "ㅙ", "ㅚ", "ㅛ", "ㅜ", "ㅝ", "ㅞ", "ㅟ", "ㅠ", "ㅡ", "ㅢ", "ㅣ"]; m.rJongKE = ["", "ㄱ", "ㄱㄱ", "ㄱㅅ", "ㄴ", "ㄴㅈ", "ㄴㅎ", "ㄷ", "ㄹ", "ㄹㄱ", "ㄹㅁ", "ㄹㅂ", "ㄹㅅ", "ㄹㅌ", "ㄹㅍ", "ㄹㅎ", "ㅁ", "ㅂ", "ㅂㅅ", "ㅅ", "ㅅㅅ", "ㅇ", "ㅈ", "ㅊ", "ㅋ", "ㅌ", "ㅍ", "ㅎ"]; m.rJong = ["", "ㄱ", "ㄲ", "ㄳ", "ㄴ", "ㄵ", "ㄶ", "ㄷ", "ㄹ", "ㄺ", "ㄻ", "ㄼ", "ㄽ", "ㄾ", "ㄿ", "ㅀ", "ㅁ", "ㅂ", "ㅄ", "ㅅ", "ㅆ", "ㅇ", "ㅈ", "ㅊ", "ㅋ", "ㅌ", "ㅍ", "ㅎ"]; m.splitHangul=function(str) { let res=[]; res.originalStr=str; res.splitted3=""; res.splitted=""; let cho, jung, jong; for (let i=0;i<str.length;i++) { let c=str.charAt(i) let n=str.charCodeAt(i); if (n>=0x3131&&n<=0x3163) { // 자음 'ㄱ', 'ㄲ', 'ㄳ' 만 있는경우. [Ex] 'ㄲ'=>'ㄱㄱ', 'ㄳ'=>'ㄱㅅ' 등. n-=0x3131; res[i]={"char":c, "splitted3":c, "splitted":m.jamoKE[n]}; } else if (n>=0xAC00&&n<=0xD7A3) { // 한글일 경우 처리. n-=0xAC00; jong=n%28; jung=( (n-jong)/28 )%21; cho=( ((n-jong)/28)-jung )/21; res[i]={"char":c , "splitted3":m.rCho[cho]+m.rJung[jung]+m.rJong[jong] , "splitted":m.rChoKE[cho]+m.rJungKE[jung]+m.rJongKE[jong]}; // splitted3 는 초/중/종 으로만 나눈거고, splitted 는 초/종 도 완전히 펼쳐진 형태로. } else { res[i]={"char":c, "splitted3":c, "splitted":c}; } res.splitted3+=res[i].splitted3; // splitted3 끼리 이어놓은 string. res.splitted+=res[i].splitted; // splitted 끼리 이어놓은 string. } return res; }; ```/ Function m.splitHangul 은 한글일 경우 초/중/종 및 자음끼리 맡붙어 있는것들도 처리해주는 함수. ### Fuzzy search 할 list 들 모으기. 기본 variables. ```[.linenums.scrollable] m.fs=[]; m.fs[0]=[]; m.fs[0]["pattern"]=m.splitHangul("$!@#"); m.fs.fullList=[]; let $list=$(".docuK li"); for (let i=0;i<$list.length;i++) { let $listI=$list.eq(i); let $sec=$listI.parents(".docuK>.sec"); let txt=""; let html=""; if ($sec.exists()) { let cat=$sec.find("h2:first-child .head-txt").text(); let $subsec=$listI.parents(".subsec"); if ($subsec.exists()) { cat+="\n  -- "+$subsec.find("h3:first-child .head-txt").text(); let $subsubsec=$listI.parents(".subsubsec"); if ($subsubsec.exists()) { cat+="\n    -- "+$subsubsec.find("h4:first-child .head-txt").text(); } } txt=cat.replace(/\n   /g,"").replace(/\n /g,"")+"\n"; html='<div class="cat">'+cat.replace(/\n/g, "<br>")+'</div>'; } txt+="* "+$listI.text(); html+='<div class="li">* '+$listI.html()+'</div>'; m.fs.fullList[i]={i:i, "txt":m.splitHangul(txt), "html":html, "$listI":$listI}; } ```/ ### Trivial functions. ```[.linenums.scrollable.lang-js] RegExp.quote=function(str) { return str.replace(/[.?*+^$[\]\\{}()|-]/g, "\\$&").replace(/\s/g, "[\\s\\S]"); }; m.arrayRegExs=function(str) { let res=[]; for (let i=0;i>str.length;i++) { let c=str.charAt(i); let mapKE=m.mapKE[c]; if (mapKE) { res.push( new RegExp("["+c+mapKE+"]", "ig") ); } else { res.push( new RegExp(RegExp.quote(c), "ig") ); } } return res; }; ```/ ### Match 된 곳 highlight 시키는 function. ```[.linenums.scrollable.lang-js] m.highlightStrFromIndices=function(strSplitted, indices) { let res=""; for (let i=0, j=1, k=0, p1=0, p2=0;j<=indices.length;i=j,j++) { while (j<indices.length&&indices[j-1].end===indices[j].start) { j++; } for (;k<strSplitted.length;k++) { p1=p2; p2=p1+strSplitted[k]["splitted"].length; if (p2<=indices[i].start) { strSplitted[k]["matched"]=false; } else if (p1<indices[j-1].end) { strSplitted[k]["matched"]=true; } else { if (j===indices.length) { for (;k<strSplitted.length;k++) { strSplitted[k]["matched"]=false; } } p2=p1; break; } } } for (let i=0;i<strSplitted.length;) { if (strSplitted[i]["matched"]) { res+='<span class="bold">'; while (i<strSplitted.length&&strSplitted[i]["matched"]) { res+=m.escapeHTML(strSplitted[i]["char"]); i++; } res+='</span>'; } else { while (i<strSplitted.length&&!strSplitted[i]["matched"]) { res+=m.escapeHTML(strSplitted[i]["char"]); i++; } } } return res; }; ```/ ### Match Score from Indices 기본적으로 와 에 따라 점수를 줌. 한글의 경우 초성에 영어의 경우도 word 앞자리에 match 되었을 경우에 점수를 8점 더 줌. ```[.linenums.scrollable.lang-js] m.matchScoreFromIndices=function(strSH, ptnSH, indices) { let res=0; for (let i=0;i<indices.length;i++) { if (strSH.pCho[indices[i].start]) res+=8; } for (let i=1;i<indices.length;i++) { let diff=indices[i].start-indices[i-1].start; if (diff<5) res+=8*(5-diff); } return res; }; ```/ ### Main function :: m.fuzzySearch(ptnSH, fs) Main function :: fuzzySearch(ptnSH (pattern splitHanguled), fs (fuzzy search result)) ```[.linenums.scrollable.lang-js] m.fuzzySearch=function(ptnSH, fs) { let list=[]; if (ptnSH.splitted.indexOf(fs[0].ptnSH.splitted)===0) { fs[1]=fs[0]; } else if (fs[1] && ptnSH.splitted.indexOf(fs[1].ptnSH.splitted)===0) { if (ptnSH.splitted===fs[1].ptnSH.splitted) { return fs[1]; } } else { fs[1]=null; } if (fs[1]&&fs[1].sorted) { let sorted=fs[1].sorted; for (let i=0;i<sorted.length;i++) { list.push(fs.fullList[fs[1][sorted[i]].i]); } } else { list=fs.fullList; } let res=[]; res.ptnSH=ptnSH; let regExs=m.arrayRegExs(ptnSH.splitted); for (let i=0;i<list.length;i++) { if (regExs.length>0) { let txt=list[i].txt; let txtS=txt.splitted; regExs[0].lastIndex=0; let exec=regExs[0].exec(txtS); let matched=(exec!==null); let indices=[]; if (matched) { indices[0]={start:exec.index, end:regExs[0].lastIndex}; } for (let j=1;matched&&(j<regExs.length);j++) { regExs[j].lastIndex=regExs[j-1].lastIndex; exec=regExs[j].exec(txtS); matched=(exec!==null); if (matched) { indices[j]={start:exec.index, end:regExs[j].lastIndex}; } } if (matched) { let maxMatchScore=m.matchScoreFromIndices(txt, ptnSH, indices); let indicesMMS=[]; // indices of max match score for (let p=0;p<indices.length;p++) { indicesMMS[p]=indices[p]; // hard copy of indices } for (let k=indices.length-2;k>=0;) { regExs[k].lastIndex=indices[k].start+1; exec=regExs[k].exec(txtS); matched=(exec!==null); if (matched) { indices[k]={start:exec.index, end:regExs[k].lastIndex}; } for (let j=k+1;matched&&(j<regExs.length);j++) { regExs[j].lastIndex=regExs[j-1].lastIndex; exec=regExs[j].exec(txtS); matched=(exec!==null); if (matched) { indices[j]={start:exec.index, end:regExs[j].lastIndex}; } } if (matched) { let matchScore=m.matchScoreFromIndices(txt, ptnSH, indices); if (matchScore>maxMatchScore) { maxMatchScore=matchScore; for (let p=0;p<indices.length;p++) { indicesMMS[p]=indices[p]; // hard copy of indices } } k=indices.length-2; } else { k--; } } res.push({i:list[i].i, maxMatchScore:maxMatchScore, highlight:m.highlightStrFromIndices(txt, indicesMMS)}); } } else { res.push({i:list[i].i, maxMatchScore:0}); }} // sorting... let sorted=res.sorted=[]; for (let i=0;i<res.length;i++) { sorted[i]=i; } for (let i=1;i<sorted.length;i++) { let temp=sorted[i]; let j=i; for (;(j>0) && (res[sorted[j-1]].maxMatchScore<res[temp].maxMatchScore);j--) sorted[j]=sorted[j-1]; sorted[j]=temp; } return res; }; ```/ ### Special keys (ESC, up, down) :: $fuzzy_search.on("keydown") ```[.linenums.scrollable.lang-js] $fuzzy_search.on("keydown", function(e) { e.stopPropagation(); switch (e.keyCode) { case 27: // ESC = 27 e.preventDefault(); $out_focus.focus(); $fuzzy_search_container.hide(); break; case 38: // up = 38 case 40: // down = 40 e.preventDefault(); let $fsl=$fuzzy_search_list; let $lis=$fsl.find(".list-item"); let $liSelected=$fsl.find(".list-item.selected").eq(0); let $liTo=null; if ($liSelected.exists()) { if (e.keyCode===38) { $liTo=$liSelected.prev(); } else { $liTo=$liSelected.next(); } if ($liTo.exists()) { $liTo.eq(0).trigger("click"); if ($liTo.offset().top<$fsl.offset().top+2) { // $liTo at upside of scroll. $fsl.scrollTop($fsl.scrollTop()+$liTo.offset().top-$fsl.offset().top-2); } else if ($liTo.offset().top+$liTo.outerHeight()>$fsl.offset().top+$fsl.height()+2) { // $liTo at downside of scroll. $fsl.scrollTop($fsl.scrollTop()+$liTo.offset().top+$liTo.outerHeight()-$fsl.offset().top-$fsl.height()-2); } } } else { if ($lis.exists()) { if (e.keyCode===38) { $liTo=$lis.last(); $fsl.scrollTop($fsl[0].scrollHeight); } else { $liTo=$lis.first(); $fsl.scrollTop(0); } $liTo.eq(0).trigger("click"); } } break; } }); ```/ ### Do Fuzzy Search Delayed (Lazy) Loading 이랑 비슷하게 구현. 이렇게 해야만 속도가 빨라지고, UX 가 좋아지는듯도? 아닌가? clearTimeout, setTimeout 만 써서도 만들어 봤었는데... 너무 느리길래 이렇게 바꾼거긴 한데... ```[.linenums.scrollable.lang-js] m.doFS=function() { let fsPtnSH=m.splitHangul($fuzzy_search.text()); if (m.fs[0].ptnSH.splitted!==fsPtnSH.splitted) { m.fuzzySearch(fsPtnSH, m.fs); let res=m.fs[0]; let sorted=res.sorted; let str=""; for (let i=0;i<sorted.length;i++) { let k=res[sorted[i]].i; str+='<div class="list-item" onclick="m.gotoLi(event,this,'+k+')">' +m.fs.fullList[k]["html"] +((res[sorted[i]]["highlight"]!==undefined)? '<div class="highlighted">'+'<span class="maxMatchScore">'+res[sorted[i]].maxMatchScore+'</span> :: '+res[sorted[i]]["highlight"]+'</div>':'') +'</div>'; } $fuzzy_search_list.html(str); $fuzzy_search_list.scrollTop(0); m.$fsLis=$fuzzy_search_list.find(".list-item"); } }; m.previous=Date.now(); m.fsOn=function() { let now=Date.now(); let passed=now-m.previous; if (passed>m.wait) { m.doFS(); m.previous=now; } else { $fuzzy_search.off("input.fs keyup.fs cut.fs paste.fs"); setTimeout(function() { m.doFS(); m.previous=Date.now(); $fuzzy_search.on("input.fs keyup.fs cut.fs paste.fs", m.fsOn); }, m.wait*1.1-passed); } }; $fuzzy_search.on("input.fs keyup.fs cut.fs paste.fs", m.fsOn); $fuzzy_search.trigger("keyup"); ```/ ### Result (JSON) JSON 형태의 Result ```[.linenums.lang-java] // Fuzzy search 결과를 저장할 변수들. m.fs=[]; m.fs[0]=[]; m.fs[0]["ptnSH"]=m.splitHangul("$!@#"); // m.splitHangul 결과는 {"char":"꺆", "splitted3":"ㄲㅑㄲ", "splitted":"ㄱㄱㅑㄱㄱ"}; // Fuzzy search 할 string list 가 다음과 같이 존재함. m.fs.fullList=[]; m.fs.fullList[i]={i:i, "txt":m.splitHangul(txt), "html":html, "$listI":$listI}; // m.splitHangul 결과는 {"char":"꺆", "splitted3":"ㄲㅑㄲ", "splitted":"ㄱㄱㅑㄱㄱ"}; // Fuzzy search 결과는 다음과 같이 저장됨. m.fs=[]; m.fs[0]=[]; // 이번 fuzzy search 결과. m.fs[1]=[]; // 1번전의 fuzzy search 결과. // 스마트폰에서 한글 입력시 "ㄱ,ㄲ" 가 바뀌면서 입력되는 형태도 있으니... 한글자만 지우고 다시 입력하는 경우도 빈번하고... m.fs[0]["ptnSH"]=m.splitHangul("김"); m.fs[1]["ptnSH"]=m.splitHangul("기"); // "김" 검색했다가 "깁" 같은걸로 바꿔서 검색하는 경우 m.fs[1] 을 참고해서 후속 검색. // "김ㅂ" 을 검색한다면 m.fs[0] 를 참고해서 후속 검색하는거고. m.fs[1]=m.fs[0]; // 아무튼 on, off, setTimeout 등을 잘 이용해서 구현. ptnSH.splitted.indexOf(fs[0].ptnSH.splitted)===0 같은 query 이용해서 효율적으로 동작하도록 해놓음. // 결과는 index 들 모아놓고, 각각의 max match score 저장해놓고, 그때의 match 위치들 indices 저장 (highlighted string html만?) 해놓고, sorted index (DESC maxMatchScore) 도 저장. m.fs[0][0]={i:i, maxMatchScore:xxx, highlight:xxxx}; fsResult[0]["sorted"]=[sorted i's]; // sorted indices 를 따로 저장해놓을까나? m.fs[0]=[]; m.fs[0].ptnSH=m.splitHangul(pattern); m.fs[0][0]={i:list[i].i, maxMatchScore:maxMatchScore, highlight:m.highlightStrFromIndices(txt, indicesMMS)}); m.fs[0][1]={i:list[i].i, maxMatchScore:maxMatchScore, highlight:m.highlightStrFromIndices(txt, indicesMMS)} ....... m.fs[0].sorted=[9,2,4,1,7,3,5,8,6]; // m.fs.fullList 에서 찾으려면, m.fs.fullList[fs[0][sorted[i]].i] ```/ ## prefix 명령어? Sublime text 에서는 @, #, : 등은 prefix 를 이용해서 조금 다른 방식으로 fuzzy search 가 동작하도록 해놨는데, 나도 이런게 좀 필요하긴 할듯? 여러 단어를 입력받고 그 단어들간의 순서는 중요하지 않지만 더 겹치는게 많은 string 을 뽑아낸다던지 하는 방식으로? 특정 reco 에 어울리는 category 를 찾는다고 할 때, 이 reco 의 제목에서 자동으로 어울리는 category 를 match 시켜준다던지 할때 유용할거 같은데... 아님 글쓴이가 내 글은 이런이런 단어들이 keyword 라고 설정해놓고 reco 버튼을 추가해 놓으면 그 keyword 들 가지고 적절한 category 를 찾아준다던지 할때... 아무튼 여러 형태/방식으로 fuzzy search 를 변형/구체화/세분화 할 수 있으면 좋은점이 많을듯. ## 입력때마나 검색에 해당하는지 check 하기. (바로전 search 내역만 기억해놓기?) 검색해야할 string list 가 그리 크지 않거나, user-specific 한 경우에는 검색어에 대해 미리 indexing 해놓는게 그리 효율좋은 방법은 아닐테니, 그냥 검색어 입력받을때마나 그때그때 match 시켜보고 match score 구하고 정렬하는게 맞는 방법 같음. 핸드폰으로 검색어 입력할때는 하나하나씩 입력하다가 하나씩 지우고 다시쓰는 경우가 빈번하니 바로전 search 결과는 저장해놓는게 좋아보이기도 함. ## Indexing : 검색 결과를 모두 table 에 미리 저장해두기?

이 부분은 아직 정리 덜했음. 아이디어만... 검색해야 하는 string list 가 엄청나게 크다던가, 추가로 여러 사람이 같은 data (string list) 에 대해 검색하는 경우라면 이런 indexing 이 더 좋은방법 같긴 함. User-specific 이라도 꽤나 자주 검색을 사용한다던가 하는 경우도 indexing 이 더 검색효율을 좋게 만들어 줄지도?

무식하게는 category list 의 모든 가능성을 indexing 으로 저장해 놓고 뽑아 쓰는 것일텐데... "abcde" 가 있으면 "a", "b", "c", "d", "e", "ab", "ac", "ad", "ae", "bc", "bd", "be", "cd", "ce", "de", "abc", "abd", "abe", "acd", ...... 이런식으로만 쳐도 "abcde"가 뜨는식. "abaaabbc" 도 있다면 "abc" 를 치면 ["abcde", "abaaabbc"] 가 다 떠야함. (정렬순서는 match score 따라서.) 뭐 실제 어떻게 동작하는지, 얼마나 편하지는 쓰면서 느껴봐야 제대로 체감할듯. 무식하게 위와 같이 1차원 배열 식으로 할수는 없을테고 (짜기는 쉽겠지만 메모리를 많이 잡아먹을듯? 아닌가? 그냥 이렇게 무식하게 해서 Hash table 에 넣어놓는게 성능면에서 가장 좋을듯도 하고...), 조금 더 체계적으로는 chainning 이나 recursive 쓰면 될거 같은데? 더 복잡해지기만 하나? ```[.linenums.scrollable] 가장 무식하게 Hash table 만들기. // "abcde" 가 list 에 있다면, e: "e" -> [] de: "d" -> [e] cde: "c" -> [de, e] bcde: "b" -> [cde, de, e] abcde: "a" -> [bcde, cde, de, e] // 와 같은 JSON 비스무레 한 것이 있으면 될듯? JSON 식의 tree 구조를 생각해 봤는데 안될듯함 ㅡㅡ;;;;, 제대로 동작하게 하려면 구조가 너무 복잡해지거나. (복잡하면 그냥 무대뽀식의 hash table 보다 나을게 없음.) 원하는대로 동작되는 복잡한 구조도 당장 생각이 안남. // 위를 조금 더 풀어서 쓰자면, catList["e"].push("abcde"); // Value 가 저장되나? Reference (string address) 만 저장되는게 좋은데... catList["d"].push("abcde"); catList["de"].push("abcde"); catList["c"].push("abcde"); catList["cd"].push("abcde"); catList["cde"].push("abcde"); catList["ce"].push("abcde"); catList["b"].push("abcde"); catList["bc"].push("abcde"); catList["bcd"].push("abcde"); catList["bcde"].push("abcde"); catList["bce"].push("abcde"); catList["bd"].push("abcde"); catList["bde"].push("abcde"); catList["be"].push("abcde"); catList["a"].push("abcde"); catList["ab"].push("abcde"); ...... ...... catList["ae"].push("abcde"); // 와 같은 Hash table 이 만들어 지는 것. "bd" 가 입력되었다면, catList["bd"] 에 저장되어 있는 list 들을 뽑아냄. // "ze" 가 추가로 list 에 들어간다면, e: "e" -> [] ze: "z" -> [e] // 위를 더 풀어서 쓰자면, catList["e"].push("ze"); catList["z"].push("ze"); catList["ze"].push("ze"); // 와 같이 됨. 1 1 + (1) 1 + (1+(1)) + (1) 1 + (1+(1+(1))+(1)) + (1+(1)) + (1) 1 + (1+(1+(1+(1))+(1))+(1+(1))+(1)) + (1+(1+(1))+(1)) + (1+(1)) + (1) ```/ \begin{align*} a_1 &= 1 \\ a_n &= 1 + \sum_{i=1}^{n-1} a_i \end{align*} 이건 무슨 수열이지? 아무튼 글자 길이에 따라 hash table 크기가 기하급수적(?)으로 증가해야만 해서 무리일듯. 그냥 매번 line by line match/search 를 하는게 나을거 같기도... 매 session (put reco 관련 창을 열고 닫을때) 마다 hash table 을 만들었다 버리는게 더 cost 가 많을것도 같아서. ```[.linenums] // "bd" 를 검색하고 싶다면, let re = /.*b.*d.*/i; // or: let re = new RegExp(".*b.*d.*", "i"); re.test("abcde"); // return true; re.test("aBcDe"); // return true; re.test("abbcdde"); // return true; re.test("ABDEE"); // return true; ```/ Category 가 ; 구분자로 여러개 들어갈 수 있어서 이런것도 처리해줘야 할텐데... 완성된 cat 은 boxed 로 묶어서 보기 쉽게 만들어도 줘야 하겠고... x 버튼 (클릭으로 지우기) 같은 것도 생각해봐야겠고... 왜이리 많니? ;, -- 관련해서 format 도 잘 갖춰져 있는지 javascript 에서 test 해주는게 좋을듯. 적절한 위치에 list up 이 보여야 하고. 너무 많으면 scroll, 적을땐 그 화면에 맞춰서. (css: max-height) 설정으로 조정해줘야 할듯? Bubble refer 때 썼던 position 응용하고. 확실히 sublime 이 잘되어 있어서 잘 참조해야 할듯.

정렬순서도 중요해 보이긴 함. (지금은 그냥 catList 순서대로만 보여줌.) 이건 UX 를 어떻게 디자인 할까랑도 연결될듯? 첫 char 위치가 적은 순서대로 보여준다던지... ## RRA

1. Sublime text
2. Wiki - Approximate string matching
3. crossplatform.net - Sublime Text Ctrl+P Like Fuzzy Matching In Few Lines of Python, 2013-06-16, by Raahul Seshadri
4. blog.amjith.com :: FuzzyFinder - in 10 lines of Python, 2015-06-23
5. juggernaut.tistory.com :: 퍼지 문자열 검색 (Fuzzy string search), 2012-12-27, by 임은천
   원문 : Нечёткий поиск в тексте и словаре, 2011-03-09, by Никита Сметанин (러시아어인듯)
   영어번역 : NIKITA'S BLOG :: Fuzzy string search, 2011-03-24
   // 다양한 형태/방법의 fuzzy search 에 관해 설명.