선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 논문은 터치 스크린을 이용하는 소프트 키보드에서 사용자의 오타를 줄일 수 있는 알고리즘을 설계하고 안드로이드 스마트폰에 구현하여 알고리즘을 현실화하는 기초 연구이다. 우리는 3 단계로 구성되는 워드 추천 알고리즘을 제안하고 성능을 평가하였으며, 좋은 성능 결과를 얻게 되었다.
- 본 연구에서는 입력된 텍스트 T와 철자가 유사한 워드들을 사전에서 골라내기 위해 Edit Distance 알고리즘을 수정하여 Modified Edit Distance(MED)를 고안하였다. 사용자가 입력한 워드 T와 사전에 있는 단어 W와의 편집 거리를 ed(T, W) 라고 하고, 단어 W의 철자 개수를 Size(W)라고 할 때, T와 W의 med는 다음과 같이 계산한다.
- 인터넷 상에서 크롤링하여 선택하였기 때문에 각 워드의 사용빈도수는 인터넷을 사용하는 사용자들의 평균적인 빈도이다. 본 연구에서는 키가 입력될 때마다 사용자가 입력한 워드의 사용 빈도를 지속적으로 변경한다.
제안 방법
- 본 논문에서 제안한 알고리즘을 테스트하기 위해 안드로이드 플랫폼에 그림 3과 같은 구조로 소프트 키보드를 구현하였다. PC에서 웹 상에서 사용되는 빈도수가 높은 워드 중 2500개를 추려내고, Hash Code Generator를 이용하여 각 워드의 해시 코드를 생성하여 Phone DB를 구성한다.
- 동시에 현재까지 입력된 텍스트를 Word Recommender(추천 모듈)로 전달한다. Word Recommender는 Hash Code Generator를 호출하여 입력된 텍스트를 해시 코드로 변환하고, 본 논문에서 제안된 추천 알고리즘을 이용하여 사전을 검색하여 워드를 추천한다. 추천된 워드는 추천 창에 출력한다.
- 지금까지 연구의 대부분은 키 배치나 사용자 입력을 예측하여 추천하는 방법을 통해 사용자 오타 입력을 줄이는데 초점이 맞추어져 왔다. 그러나 본 연구에서는 오타의 경우를 줄이기보다는, 텍스트를 입력하는 동안 사용자가 의도하는 입력을 추론하여 이를 추천함으로써 오타가 발생하는 경우 사용자가 빠르게 교정할 수 있게 하여 사용자의 키 입력 편리를 도모하는 추천 키 입력 시스템을 제안하고 MissLess로 불리는 소프트 키보드를 구현하였다.
- 그러므로 본 연구에서는 실제 상황과 유사한 실험을 위해, 사용자의 행위를 사전에 테스트 셋으로 만들어 두고 알고리즘이 구현된 키보드 소프트웨어에 배치(batch) 방식으로 전달하여 성능을 테스트한다. 테스트에 사용되는 단위 데이터는 ‘정상 워드’와 ‘오타 워드’로 구성되며, 오타 워드를 입력으로 주었을 때, 정상 워드가 추천 리스트에 포함되면 추천 성공으로 판별한다.
- 사용자가 키를 입력할 때마다 현재 입력된 텍스트 Word를 해시 정수로 변환하고, 어휘 사전에 있는 각 워드의 해시 값과 비교하여 일정 범위 내의 차이를 가진 모든 워드를 해시 값 순서로 정렬하여 워드 리스트를 만든다(해시필터). 그리고 다시 Word와 워드 리스트의 각 워드에 대해 철자 유사성을 비교하여 철자 유사성이 높은 순위로 재정렬한다(철자유사성 기반 정렬). 그리고 다시 워드리스트에 있는 상위 워드 중에서 사용자의 사용 빈도수가 높은 워드를 우선적으로 N개(현재 4개) 선정하여 최종 추천한다(사용자패턴기반 추천).
- 그리고 다시 Word와 워드 리스트의 각 워드에 대해 철자 유사성을 비교하여 철자 유사성이 높은 순위로 재정렬한다(철자유사성 기반 정렬). 그리고 다시 워드리스트에 있는 상위 워드 중에서 사용자의 사용 빈도수가 높은 워드를 우선적으로 N개(현재 4개) 선정하여 최종 추천한다(사용자패턴기반 추천).
- 일반 커뮤니티 사이트를 통해 자주 사용된 워드 1500개 중에서 랜덤하게 100개를 추출하였다. 그리고 본 연구의 보조원들이 이 워드들에 대해서 직접 타이핑하면서 발생하는 오타로 테스트 셋을 구성하였다.
- 사용자가 소프트 키보드로 텍스트를 입력하면 키가 입력될 때마다 입력된 워드 T의 해시 코드 C를 계산하고 C 값에서 일정 범위의 해시 값을 가진 워드를 어휘 사전에서 추출한다. 그리고 추출된 워드들과 T의 편집 거리(Edit Distance)를 계산하여 T와 편집 거리가 가장 가까운 순서로 정렬하고, 높은 순위 워드들을 대상으로 사용자의 사용 빈도수를 반영하여 추천 워드를 결정한다.
- 따라서 두 워드에서 동일한 글자가 첫 글자인 경우와 마지막 글자인 경우 해시 값에 다른 영향을 주도록 계수(Letter Weight) α(alpha)를 도입하여 해시 함수를 구성한다.
- 본 논문에서 제안하는 알고리즘은 사용자가 입력한 텍스트에 대해 추천 워드를 선택하기 위해, 두 워드 사이의 유사성을 판단하는 과정을 가지고 있다.
- 본 논문에서 제안한 알고리즘을 테스트하기 위해 안드로이드 플랫폼에 그림 3과 같은 구조로 소프트 키보드를 구현하였다. PC에서 웹 상에서 사용되는 빈도수가 높은 워드 중 2500개를 추려내고, Hash Code Generator를 이용하여 각 워드의 해시 코드를 생성하여 Phone DB를 구성한다.
- 또한 delegate가 delete가 되려면 g, a가 삭제되어야 하므로 두 단어의 Edit Distance는 2가 되며, park이 spark가 되기 위해서는 s를 삽입하고, r을 k로 대치하고, k를 e로 대치해야 하므로 Edit Distance는 3이 된다. 본 논문에서는 Edit Distance 알고리즘을 수정한 Modified Edit Distance를 제안하고 사용하였다.
- 본 논문에서는 어휘 사전에 저장된 각 워드마다 해시 코드 정수 값을 할당한다. 해시 코드의 목적은 워드들의 유사성을 쉽게 분류하기 위해서이다.
- 본 연구를 도와주는 보조원들의 ‘카카오톡’ 메신저 그룹 채팅에서 자주 사용된 단어를 랜덤하게 100개 추출하여 ‘정상 워드’로 구성하고, 각 정상 워드에 대해 직접 타이핑해보며 가장 많이 발생하는 오타를 ‘오타 워드’로 설정하였다.
- 어휘 사전은 일반적으로 많이 사용하는 워드와 사용자가 주로 사용하는 워드가 합쳐져 구성되며, 각 워드별로 하나의 해시 정수 값이 할당되어 함께 저장된다. 사용자가 키를 입력할 때마다 현재 입력된 텍스트 Word를 해시 정수로 변환하고, 어휘 사전에 있는 각 워드의 해시 값과 비교하여 일정 범위 내의 차이를 가진 모든 워드를 해시 값 순서로 정렬하여 워드 리스트를 만든다(해시필터). 그리고 다시 Word와 워드 리스트의 각 워드에 대해 철자 유사성을 비교하여 철자 유사성이 높은 순위로 재정렬한다(철자유사성 기반 정렬).
대상 데이터
- 본 논문에서 다루는 사전은 인터넷에서 주로 사용되거나 사용자가 자주 사용하는 워드로 구성된다. 각 워드 W는 참조 카운트 R, 해시 코드 C와 함께 다음과 같이 사전에 저장된다.
- 사전에 포함되는 어휘 개수는 모바일 단말기의 메모리 량을 고려하여 적당히 결정한다. 본 연구에서 안드로이드 스마트폰에 2500개 어휘를 사용하였다.
- 본 연구에서는 실험을 위해 TS1, TS2, TS3 등 3개의 테스트 셋을 구성하였다.
- 본 연구의 성능 평가 지수는 추천 성공률이다. 사용자가 입력하고자 하는 어휘가 추천 리스트에 존재하면 추천 성공으로 본다.
- 일반 커뮤니티 사이트를 통해 자주 사용된 워드 1500개 중에서 랜덤하게 100개를 추출하였다. 그리고 본 연구의 보조원들이 이 워드들에 대해서 직접 타이핑하면서 발생하는 오타로 테스트 셋을 구성하였다.
- 일반 커뮤니티 사이트를 통해 추출한 워드 중에서 사용률이 가장 떨어지는 워드 1000개를 선정하고 이 중에서 100개를 랜덤하게 선택하였다. 그리고 본 연구의 보조원들이 이 워드들에 대해서 직접 타이핑하면서 발생하는 오타로 테스트 셋을 구성하였다.
- 테스트에 사용되는 단위 데이터는 ‘정상 워드’와 ‘오타 워드’로 구성되며, 오타 워드를 입력으로 주었을 때, 정상 워드가 추천 리스트에 포함되면 추천 성공으로 판별한다.
성능/효과
- 두 번째, 사용자들의 입력 습관상 오타는 발견 즉시 수정하기 때문에 여러 글자로 이루어지는 워드에서 뒤에 입력된 글자에 오타가 생길 가능성이 매우 높고, 첫 번째 글자가 서로 다른 두 워드는 유사성이 매우 낮다. 따라서 두 워드에서 동일한 글자가 첫 글자인 경우와 마지막 글자인 경우 해시 값에 다른 영향을 주도록 계수(Letter Weight) α(alpha)를 도입하여 해시 함수를 구성한다.
- 추천 성공률을 실험한 결과는 표 3과 그림 5에서 보여준다. 실험 결과에 의하면 TS2의 추천 성공률이 97%에 이르렀지만 테스트 셋에 따라 추천 성공률이 다르게 나타났다. TS1의 추천 성공률이 특히 낮은데 이것은 TS1은 특정 사용자 집단의 ‘카카오 톡’에서 사용된 어휘를 대상으로 하였기 때문에, 인터넷에서 주로 사용되는 어휘를 대상으로 구성된 어휘 사전에는 없는 어휘가 많기 때문이다.
- 본 논문은 터치 스크린을 이용하는 소프트 키보드에서 사용자의 오타를 줄일 수 있는 알고리즘을 설계하고 안드로이드 스마트폰에 구현하여 알고리즘을 현실화하는 기초 연구이다. 우리는 3 단계로 구성되는 워드 추천 알고리즘을 제안하고 성능을 평가하였으며, 좋은 성능 결과를 얻게 되었다.
- 결론적으로 본 논문의 기여는 다음과 같다. 첫째, 제안된 알고리즘은 장치와 무관하게 키입력 오류를 줄인다. 둘째, 사용자의 입력 워드를 고려한 개인화(personalized) 키 입력 시스템이고, 맞춤법과 무관하게 작동하므로 사용자의 실제 습관에 부합된 키보드이다.
- 첫째, 테스트 셋의 크기가 부족하고, 테스트 셋에 포함되는 ‘정상 워드’와 ‘오타 워드’가 실험자의 개인적인 것이어서, 실험의 현실성이 떨어진다.
후속연구
- 첫째, 테스트 셋의 크기가 부족하고, 테스트 셋에 포함되는 ‘정상 워드’와 ‘오타 워드’가 실험자의 개인적인 것이어서, 실험의 현실성이 떨어진다. 둘째, 워드 리스트 Lh나 Lmed 리스트의 크기에 비례하여 실행 시간이 길어지게 되므로 이에 대한 대책이 필요하다. 셋째, 사용자가 많이 사용하는 단어에 대한 추천 성공률을 높이는 알고리즘의 개선이 필요하다.
- 둘째, 워드 리스트 Lh나 Lmed 리스트의 크기에 비례하여 실행 시간이 길어지게 되므로 이에 대한 대책이 필요하다. 셋째, 사용자가 많이 사용하는 단어에 대한 추천 성공률을 높이는 알고리즘의 개선이 필요하다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.