검색어 자동완성

v1.1 2007/12/22 Copyleft by 전경헌@사이냅소프트

사용자 삽입 이미지

사람들은 이미 검색해 본 것을 검색한다.
검색어에도 멱함수의 법칙이 존재.
팔레토의 법칙 20%의 검색어가 80%를 차지한다.

1. 재료 준비

검색어와 우선순위를 준비한다.

우선순위란 자동완성에 적용되는 검색어가 많을 경우에
우선적으로 상위에 보여줄 몇개를 선별하는 기준이 된다.

우선순위는 기본적으로 로그를 통해서 얻어지고,
마케팅적인 이유로 인위적인 조작이 할 수도 있다.

회사 인트라원의 고객명입력에 대해서 검색어 자동완성을 해보자.
우선순위를 찾기위해 현재까지 등록된 고객노트 건수를 기준으로
우선순위를 매긴다. 우선순위를 좀 더 잘 매기기 위해서 최근 3개월간의
등록 건수나 최종 등록 일자를 계산에 포함시키는 것도 고려할만하다.

현재까지 고객관리에 등록된 약 2600명의 고객명에 대해서
우선순위를 찾아내 다음과 같은 형식으로 만든다.

형식 : (우선순위, 고객명)
예)
(111, 정웅교)
(65, 김영섬)
(29, 장원식)
(12, 송성환)
(8, 박동인)
(1, 전경헌)

2. 재료 손질

요즘들어 휴대전화나 네비게이션에 자음으로만 검색하는 기능들이 생겨나서
여러가지 편리함을 주고 있는데, 자동완성에도 적용하면 좋겠다. 그러자면
각 검색어가 어떤 자음으로 만들어지는 지를 알고 있어야 한다. 즉, “전경헌”을
찾기위해 “ㅈㄱㅎ”만 입력해도 되려면 미리 검색어의 초성정보를 가지고 있어야 한다.

또한, “저”를 가지고 “전경헌”을 찾아낼 수 있도록 하는 등, 만들고 있는 중의
글자를 가지고 자동완성이 되는 것도 매우 편리할텐데, 그러자면 어떤 글자를
만들기 위해 어떤 키 입력이 필요한 지를 알고 있는 것도 필요하겠다.

그래서 재료에 대해서 두가지 손질을 할텐데, 하나는 초성에 대한 키입력,
다른 하나는 전체에 대한 키 입력이다.

(1, 전경헌, ㅈㄱㅎ, wjsrudgjs) -> (1, 전경헌, wrg, wjsrudgjs)

나머지도 마찬가지로 손질을 해둔다.

(111, 정웅교, wdr, wjddndry)
(65, 김영섬, rdt, rladudtja)
(29, 장원식, wdt, wkddnsjtlr)
(12, 송성환, ttg, thdtjdghks)
(8, 박동인, qed, qkrehddls)

손질을 위해서는 한글을 키입력으로 변환하는 간단한 프로그램을 작성해야 하는데,
쉬운 방법으로 조합형한글을 이용한다.(소스는 keys.py)

유니코드 또는 완성형 -> 조합형한글 -> 초중종성 분리 -> 초중종성에 대한 키입력
 

# 한글이나 자모에 해당하는 문자를 발견했을 경우
# 초/중/종성에 대한 키 입력값을 찾아낸다.
# 한글이 아닌경우는 cp949문자열을 반환한다.
# uch : 유니코드 문자 1개
def keytran( uch ):
  if uch_class( uch ) in [HANGUL,JAMO]:
    (a,b,c) = jasokey(uch.encode(‘johab’))
    return ”.join([a,b,c])
  else:
    return uch.encode(‘cp949’)

# 문자열을 키입력으로 변환한다.
# 초성키입력과 전체키입력 pair를 반환한다.
# h : cp949 문자열
def hankeys( h ):
  kch = []
  for uch in unicode(h,’cp949′):
    kch.append(keytran(uch))
  return ”.join(map(lambda x:x[0],kch)), ”.join(kch)


3. 자동 완성을 위한 검색

3000개도 안되는 검색어에 대해서는 별도의 자료구조 없이 메모리상에서 Full Scan을 해도
느리지 않다. (검색어가 10만개쯤 되면? 해보고 느려지면 다른 자료구조를 생각한다)

입력중인 문자열의 키값을 찾아서 해당 키값과 일치하는 검색어를 찾는다.
모든 검색어에 대해서 검색어 자체가 일치하는 것,
초성 키입력이 일치하는 것,
초중종성 전체 키입력이 일치하는 것을 찾고,
우선순위로 소팅하여,
최대 상위 max개를 리턴한다.
결과를 캐싱한다.
(소스는 ac.py, lru.py)
 

# 데이타 파일로부터 자동완성할 검색어 목록을 만든다.
# 최종적으로 만들어지는 리스트는 아래 형태를 가진다
# (가중치, 검색어, 초성키입력, 전체키입력)
def loadterms( fname ):
    terms = []
   
    f = open( fname )
    for line in f:
        if line.startswith(‘#’):
            continue
        ls = line[:-1].split(‘t’)
        keyfst, keyall = hankeys( ls[1] )
        terms.append( (int(ls[0]), ls[1], keyfst, keyall) )
    f.close()

    # 미리 소팅해 놓으면 나중에 소팅할 필요가 없다.
    terms.sort(key=lambda x:x[0], reverse=True)
    return terms

#——————————————————–
# 검색어 s를 이용하여 최대 max개의 검색 결과를 반환한다
# domain : 검색하고자 하는 대상
# s : 검색어
# max : 최대 검색결과
def dsearch(domain, s, max=10):
    if s in dsearch_cache:
        return dsearch_cache[ s ]
   
    keyfst, keyall = hankeys( s )
    res = []
    cnt = 0
    for person in domain:
        if person[1].startswith(s) or person[2].startswith(keyall) or person[3].startswith(keyall):
            res.append( person[:2] )
            cnt += 1
            if cnt >= max:
                break
   
    # 결과를 caching 한다
    dsearch_cache[ s ] = res
   
    if cnt == 0:
        return []
   
    # 미리 소팅해놓았으면 다시 안해도 된다
    #~ res.sort(key=lambda x:x[0], reverse=True)
    return res[:max]

4. 간단한 테스트

웹페이지에 붙이기 전에 우선 간단한 테스트 프로그램을 통해서
예상대로 작동하는 지 확인한다. (소스는 ac.py)

# 검색어와 일치하는 최대 10개의 결과를 우선순위에 따라 출력한다.
# domain : 검색하고자 하는 대상
# s : 검색어
def sresult(domain, s ):
  print ‘Search for ‘, s
  sres = dsearch(domain, s)
  for r in sres:
    print r[0],r[1]

if __name__ == ‘__main__’:
  domain = loadterms(‘customer.txt’)
  sresult( domain, ‘ㅈ’)
  sresult( domain, ‘ㅈㄱㅎ’)
  sresult( domain, ‘전겨’)

실행 결과

Search for  ㅈ
111 정웅교
29 장원식
Search for  ㅈㄱㅎ
1 전경헌
Search for  전겨
1 전경헌

5. 웹 입력창에 붙이자.

인터넷에서 간단한 입력창과 javascript ajax 코드를 구해서 붙여본다.
찾아낸 html 파일(ac.html)을 보니, Request 전송을 위하여 escape를 이용하고,
Reponse를 받기 위하여 name이라는 태그를 이용함을 알았다.

Requset :
  createXMLHttpRequest();
  var url = “/cgi/ac_ajax.py?p=” + escape(inputField.value);
  …

Response :
  if (xmlHttp.status == 200) {
    setNames(xmlHttp.responseXML.getElementsByTagName(“name”));

    …

여기에 해당하는 ajax 용 cgi 스크립트(ac_ajax.py)를 만든다.

#!C:/python25/python -u
# encoding=cp949
#
import cgi
params = cgi.FieldStorage()
p = params.getvalue(‘p’,”)

import urllib
p = unicode(p.replace(‘%’,’\’), ‘unicode_escape’).encode(‘euc-kr’)

print ‘Content-Type: text/xmln’
print ‘

from ac import dsearch, loadterms
sres = dsearch( loadterms(‘customer.txt’), p)
for r in sres:
    print ‘%s‘ % r[1]
print ‘‘

한글처리를 위해서 자바스크립트에서 escape된 문자열을 euc-kr로 변경하고
출력도 euc-kr로 만들어 반환한다.

ac_ajax.py를 아파치의 cgi 폴더에 올려놓고, 웹 브라우저에서 ac.html을 열어서 테스트한다.

6. 매번 로드 하겠네요.

그렇죠. 아주 않좋은 구조입니다. 검색어 하나 들어올 때마다, 모든 검색어를 로딩하는
것부터 Full Scan까지 다 합니다. 그래서 한번만 로딩하도록 적절한 방법을 고려합니다.
xmlrpc를 써서 로딩을 한번만 하도록 수정합니다.

모든 검색어를 한번만 로딩하고 검색만 전담하는 XMLRPC 서버 프로그램(xrs.py)을 만듭니다.

from ac import dsearch, loadterms
from SimpleXMLRPCServer import SimpleXMLRPCServer
from urllib import quote, unquote

class IntraCust():
    def __init__(self):
        self.domain = loadterms(‘customer.txt’)
    def suggest(self, p):
        recs = dsearch( self.domain, unquote(p))
        res = []
        for rec in recs:
            res.append( quote(rec[1]) )
        return res

if __name__==’__main__’:
    # 아래 호스트, 포트는 알아서 바꾸시길
    server = SimpleXMLRPCServer((“allen.synapsoft.co.kr”, 8000))
    server.register_instance( IntraCust() )
    server.serve_forever( )

XMLRPC가 잘 작동하는 지 확인하기 위해서 간단한 테스트를 합니다.

import xmlrpclib
server = xmlrpclib.ServerProxy(‘http://allen.synapsoft.co.kr:8000’)
res = server.suggest(‘wrg’)
from urllib import unquote
for r in res:
    print unquote( r )

여기서 잠깐, 원래 XMLRPC에서 한글이 잘 처리되도록, SimpleXMLRPCServer와 ServerProxy에 encoding이라는
파라미터를 줄 수 있습니다. 그런데, win32환경에서는 expat 파서때문인지, encoding파라미터가
잘 말을 듣지 않아서, 부득불 urllib에 있는 quote와 unquote를 사용하여 한글사용을 피했습니다.

테스트가 잘 되었으니 이제 xmlrpc를 이용하는 새로운 cgi 프로그램(ac_ajax_xmlrpc.py)를 만들어 붙입니다.

import cgi

# 자동완성을 위한 키입력을 받아서 euc-kr로 변환한다
params = cgi.FieldStorage()
p = params.getvalue(‘p’,”)
p = unicode(p.replace(‘%’,’\’), ‘unicode_escape’).encode(‘euc-kr’)

# XML-RPC로 입력을 보내고, 결과를 받는다
# 한글처리 오류를 막기위해 urllib의 quote, unquote를 썼다.
import xmlrpclib
from urllib import unquote, quote
server = xmlrpclib.ServerProxy(‘http://allen.synapsoft.co.kr:8000’)
res = server.suggest( quote(p) )

# 결과를 XML로 만들어 리턴한다
print ‘Content-Type: text/xmln’
print ‘
for r in res:
    print ‘%s‘ % unquote(r).replace(‘&’,’&’)
print ‘

7. 검색어가 100만개쯤 되면 어떻게 하죠?

자동완성을 적용해야할 중요한 검색어가 100만개쯤 된다면 구글이나 네이버이신가요?
충분히 활성화된 사이트라고 해도 자동완성에는 검색어 10만개면 충분하리라 생각됩니다.
10만개라면 메모리상에 올려놓고, 이진탐색만 해도 충분하겠고요.

진짜로 100만개에 대해서 자동완성을 해야 한다면, 메모리에 올린다 하더라도,
검색어를 Full Scan을 하는 건 좋은 방법이 아니겠네요.

파이썬에서 기본으로 지원하는 Berkeley DB를 사용해서
검색어와 키입력을 저장해놓는게 어떨까요?

MySQL같은 데이타베이스도 좋겠지만, 개인적으로 나는 버클리DB를 좋아한답니다.
이건 각 개발팀에서 숙제로 해보세요.

8. 관련해서 더 해볼 만한 것은?

apach 웹서버의 mod_xmlrpc를 이용해서 연결하는 것은 어떨까요?
python의 xmlrpc 서버가 간단하기는 하지만 튼튼해보이지는 않네요.
더 튼튼한 xmlrpc 서버를 만들어보는 것도 좋겠습니다.

자동완성 ajax의 성능이 궁금하네요. 성능테스트를 해보는 건 어떨까요?

Javascript를 더 개선해서 “와 멋지다”, “이것 참 편한데” 하는 UI를 만들어
보는 것도 의미가 있겠습니다.

조합형을 비롯한 한글코드에 대해서 더 공부해 보는 것도 좋겠죠.

autocomp_synap.zip

검색어 자동완성 python 소스 파일입니다.

사이냅 문서뷰어

어디서 어떻게 사용되고 있을까요?

사이냅 문서뷰어의 적용사례를 만나보세요

[개인정보 수집, 이용에 대한 동의 절차]

사이냅 문서뷰어 적용사례를 만나보세요

차원이 다른 HTML5 웹에디터

사이냅 에디터

사이냅 에디터가 어디에 활용될 수 있을까요?
다양한 적용사례를 만나보세요

[개인정보 수집, 이용에 대한 동의 절차]

한 차원 높은 HTML5 웹에디터를 만나보세요