KR101524740B1

KR101524740B1 - 입력 방법 편집기

Info

Publication number: KR101524740B1
Application number: KR1020117021894A
Authority: KR
Inventors: 젠칭 우; 샤오타오 두안; 타이-이 후앙
Original assignee: 구글 인코포레이티드
Priority date: 2009-03-19
Filing date: 2009-03-19
Publication date: 2015-06-01
Anticipated expiration: 2029-03-19
Also published as: US9026426B2; JP5362095B2; KR20120006489A; CN102439540A; US20120016658A1; WO2010105428A1; HK1170318A1; JP2012521025A; CN102439540B

Abstract

제1 쓰기 체계로 된 문자소를 수신하고, 제1 쓰기 체계로 된 문자소에 기초하여 제2 쓰기 체계로 된 어휘 항목들을 식별하는 입력 편집기를 구비한 방법들, 시스템들, 및 컴퓨터 프로그램 제품들을 포함하는 장치들을 개시한다. 일 구현예에서는, 방법이 제공된다. 이 방법은 제1 쓰기 체계로 된 제1 문자소를 수신하는 단계; 제2 쓰기 체계로 된 제1 형태소에 대한 제1 쓰기 체계에서의 제1 n-그램 표현을 식별하기 위해 제1 쓰기 체계로 된 문자소들의 문자소 그래프를 사용하는 단계; 형태소 그래프에서 하나 이상의 제1 노드를 찾기 위해 상기 제1 n-그램 표현을 사용하는 단계; 상기 하나 이상의 제1 어휘 항목 각각에 연관된 제1 점수에 기초하여 상기 하나 이상의 제1 어휘 항목으로부터 하나의 제1 어휘 항목을 선택하는 단계; 및 상기 제1 어휘 항목을 사용자 디바이스 상에 디스플레이를 위하여 제공하는 단계를 포함한다.

Description

입력 방법 편집기{INPUT METHOD EDITOR}

본 명세서는 입력 방법들에 관한 것이다.

쓰기 체계(writing system)는 언어의 소리들을 표현하기 위해 기호들을 사용한다. 쓰기 체계 내에 있는 기호들의 집합은 스크립트로서 불릴 수 있다. 예를 들어, 하나 이상의 로마 스크립트로 된 로마자의 집합을 포함하는 라틴 쓰기 체계가 영어를 표현하기 위해 사용될 수 있다. 라틴 쓰기 체계는 블럭화된 로마자(예컨대, 대문자화된 "B" ), 타이핑된 로마자(예컨대, 평서 문자 "b"), 및 필기체 로마자(예컨대, 필기체 문자

)를 포함한다. 문자 "b"에 대한 각 시각적 표현은 라틴 쓰기 체계에서 동일한 문자소(grapheme)를 표현한다.

다른 예시로서, 중국어는 하나 이상의 쓰기 체계에 의해 표현될 수 있다. 예를 들어, 중국어는 제1 쓰기 체계(예컨대, 병음(Pinyin), 즉 로마자화된 중국어)에 의해 표현될 수 있다. 다른 예시에서, 중국어는 제2 쓰기 체계(예컨대, 보포모포(bopomofo), 즉 주인 푸하오("Zhuyin"))을 사용하여 표현될 수 있다. 또 다른 실시예로서, 중국어는 제3 쓰기 체계(예컨대, 한지(Hanzi))를 사용하여 표현될 수 있다. 특히, 병음과 주인은 한지 문자를 표현하기 위한 표음식 체계(phonetic system)들이다.

일부 입력 방법들은 사용자가 제1 쓰기 체계로 된 텍스트를 입력할 수 있게 하고, 제2 쓰기 체계로 된 출력 후보들을 제공한다. 예를 들어, 병음 입력 방법은 사용자가 병음 스트링을 입력할 수 있게 하고, 한지로 된 출력 후보들을 생성할 수 있다. 병음 스트링은 하나 이상의 병음 음절을 포함할 수 있다. 병음 음절은 제2 서브-음절이 따라오는 제1 서브-음절(예컨대, 음절의 일부)을 포함할 수 있다. 각 병음 음절은 복수의 한지 문자에 상응하고, 각 서브-음절은 하나 이상의 로마자를 포함한다. 예를 들어, 병음 음절 "zhang"은 제1 서브-음절 "zh"과 제2 서비-음절 "ang"으로 분할될 수 있다. 또한, 서브-음절 "zh"와 "ang" 모두는 다른 병음 음절을 생성하기 위하여 다른 서브-음절과 조합될 수 있다. 예를 들어, 서브-음절 "zh"와 "a"는 병음 음절 "zha"을 생성하기 위해 조합될 수 있고, 서브-음절 "t"와 "ang"는 병음 음절 "tang"을 생성하기 위해 조합될 수 있다.

출력 후보들을 생성하는 것은 예를 들어, 입력 텍스트를 분할함으로써 입력텍스트에 있는 형태소들(예컨대, 음절들)의 식별을 요구할 수 있다.

본 명세서는 입력 방법들에 관한 기술들을 설명한다.

전반적으로, 본 명세서에서 설명된 주제의 일 양태는 제1 쓰기 체계로 된 제1 문자소(grapheme)를 수신하는 단계; 제2 쓰기 체계로 된 제1 형태소에 대한 제1 쓰기 체계에서의 제1 n-그램 표현(n-gram representation)을 식별하기 위해 제1 쓰기 체계로 된 문자소들의 문자소 그래프를 사용하는 단계―여기서, 제1 n-그램 표현은 제1 문자소를 포함함―; 형태소 그래프에서 하나 이상의 제1 노드를 찾기 위해 제1 n-그램 표현을 사용하는 단계―여기서, 형태소 그래프에서 찾은 제1 노드 각각은 제2 쓰기 체계로 된 하나 이상의 제1 어휘 항목(lexical item)을 표현하고, 하나 이상의 제1 어휘 항목 각각은 제1 n-그램 표현에 의해 표현됨―; 하나 이상의 제1 어휘 항목 각각에 연관된 제1 점수에 기초하여 하나 이상의 제1 어휘 항목으로부터 하나의 제1 어휘 항목을 선택하는 단계; 및 제1 어휘 항목을 사용자 디바이스 상에 디스플레이를 위하여 제공하는 단계의 동작들을 포함하는 방법들로 구현될 수 있다. 본 양태의 다른 실시예들은 상응하는 시스템들, 장치, 및 컴퓨터 프로그램 제품들을 포함한다.

이러한 및 다른 실시예들이 후술되는 특징들 중 하나 이상을 선택적으로 포함할 수 있다. 제1 문자소는 제2 쓰기 체계로 된 음절 일부만을 표현할 수 있다. 이 방법은 제1 쓰기 체계로 된 제2 문자소를 수신하는 단계; 제2 쓰기 체계로 된 제2 형태소에 대한 제1 쓰기 체계에서의 제2 n-그램 표현을 식별하기 위해 제1 쓰기 체계로 된 문자소들의 문자소 그래프를 사용하는 단계―여기서, 제2 n-그램 표현은 제2 문자소를 포함함―; 형태소 그래프에서 하나 이상의 제2 노드를 찾기 위해 제2 n-그램 표현을 사용하는 단계―여기서, 형태소 그래프에서 찾은 제2 노드 각각은 제2 쓰기 체계로 된 하나 이상의 제2 어휘 항목을 표현하고, 하나 이상의 제2 어휘 항목 각각은 제2 n-그램 표현에 의해 표현됨―; 제3 어휘 항목와 제4 어휘 항목으로 된 하나 이상의 순열(permutation)을 생성하는 단계―여기서, 제3 어휘 항목은 하나 이상의 제1 어휘 항목으로부터 선택되고, 상기 제4 어휘 항목은 하나 이상의 제2 어휘 항목으로부터 선택됨―; 하나 이상의 순열 각각에 연관된 제2 점수에 기초하여 하나 이상의 순열로부터 하나의 순열을 선택하는 단계―여기서, 선택된 순열은 제4 어휘 항목이 이어지는 제3 어휘 항목을 포함함―; 선택된 제1 어휘 항목의 제1 점수와 선택된 순열의 제2 점수를 비교하는 단계; 및 그 비교 결과에 기초하여, 선택된 제1 어휘 항목 또는 선택된 순열을 사용자 디바이스 상에 디스플레이를 위하여 제공하는 단계를 더 포함할 수 있다.

제1 문자소는 제2 문자소에 의해 부분적으로만 표현되는 제4 형태소와 다른 제3 형태소의 일부만을 표현한다. 문자소 그래프는 복수의 노드를 포함하고, 노드 각각은 제1 쓰기 체계로 된 문자소를 표현하고, 복수 노드의 진부분집합(proper subset of the plurality of nodes)에 있는 노드 각각은 전체 음절에 상응하고, 상응하는 전체 음절 각각은 문자소 그래프의 상응하는 노드의 문자소들과 상응하는 노드로부터 내려온 노드들의 문자소들을 포함한다. 제1 n-그램 표현은 노드들의 진부분집합에 있는 노드들 중 하나에 상응하는 전체 음절을 표현한다. 형태소 그래프는 복수 노드를 포함하고, 노드 각각은 제2 쓰기 체계로 된 하나 이상의 형태소를 표현하고, 복수 노드의 진부분집합에 있는 노드 각각은 어휘 항목에 상응하고, 상응하는 어휘 항목 각각은 형태소 그래프의 상응하는 노드의 형태소들과 상응하는 노드로부터 내려온 노드들의 형태소를 포함한다.

형태소는 한지 문자에 상응한다. 제1 n-그램 표현은 전체 병음 음절의 대표이고, 하나 이상의 어휘 항목(lexical item) 각각은 한지 용어(hanzi character)이다. 형태소 그래프에서 하나 이상의 노드를 찾기 위하여 제1 n-그램 표현을 사용하는 단계는 제1 n-그램 표현에 상응하는 문자소 그래프에 제1 노드의 식별자를 선택하는 단계; 및 식별자와 연관된 형태소 그래프에서 있는 제2 노드를 찾는 단계를 포함한다.

전반적으로, 본 명세서에서 설명된 주제의 다른 양태는 제1 로마자 입력을 수신하는 단계; 병음 입력 그래프에서 제1 병음 음절 노드를 찾기 위해 제1 로마자 입력을 사용하는 단계―병음 입력 그래프는 복수의 병음 음절 노드를 포함하고, 병음 음절 노드 각각은 하나의 로마자에 상응하고, 복수의 병음 음절 노드의 진부분집합에 있는 병음 음절 노드 각각은 하나의 병음 음절에 상응하고, 상응하는 병음 음절 각각은 병음 입력 그래프의 상응하는 병음 음절 노드의 로마자와 상응하는 병음 음절 노드로부터 내려온 병음 음절 노드들의 로마자를 포함함― ; 병음 음절 그래프에서 하나 이상의 제1 한지 문자 노드를 찾기 위해 찾은 병음 음절 노드를 사용하는 단계―병음 음절 그래프는 복수의 한지 문자 노드를 포함하고, 한지 문자 노드 각각은 하나의 병음 음절에 상응하고, 복수의 한지 문자 노드의 진부분집합에 있는 한지 문자 노드 각각은 하나 이상의 제1 한지 용어에 상응하고, 상응하는 하나 이상의 제1 한지 용어 각각은 병음 음절 그래프의 상응하는 한지 문자 노의 병음 음절들과 상응하는 한지 문자 노드로부터 내려온 한지 문자 노드의 병음 음절들에 상응하는 한지 문자들을 포함함―; 및 사용자 디바이스에 출력을 위하여, 하나 이상의 제1 한지 용어 각각에 연관된 제1 점수에 기초하여 하나 이상의 한지 문자 노드 중 하나에 상응하는 제1 한지 용어를 선택하는 단계의 동작을 포함하는 방법들로 구현될 수 있다. 본 양태의 다른 구현예들은 상응하는 시스템들, 장치, 및 컴퓨터 프로그램 제품을 포함한다.

이러한 및 다른 실시예들은 후술되는 특징 중 하나 이상을 선택적으로 포함할 수 있다. 이 방법은 제2 로마자 입력을 수신하는 단계; 병음 입력 그래프에서 제2 병음 음절 노드를 찾기 위하여 제2 로마자 입력을 사용하는 단계―여기서, 제2 병음 음절 노드는 제2 로마자 입력을 포함하는 병음 음절을 표현함―; 병음 음절 그래프에서 하나 이상의 제2 한지 문자 노드를 찾기 위하여 찾은 제2 병음 음절 노드를 사용하는 단계―여기서, 찾은 제2 한지 문자 노드 각각은 하나 이상의 제2 한지 용어에 상응함―; 제3 한지 용어와 제4 한지 용어로 된 하나 이상의 순열을 생성하는 단계―여기서, 제3 한지 용어는 하나 이상의 제1 한지 용어로부터 선택되고, 제4 한지 용어는 하나 이상의 제2 한지 용어로부터 선택됨―; 하나 이상의 순열 각각에 연관된 제2 점수에 기초하여 하나 이상의 순열로부터 하나의 순열을 선택하는 단계―여기서, 선택된 순열은 제4 한지 용어가 이어지는 제3 한지 용어를 포함함―; 선택된 제1 한지 용어의 제1 점수와 선택된 순열의 제2 점수를 비교하는 단계; 당해 비교 결과에 기초하여, 선택된 제1 한지 용어 또는 선택된 순열을 사용자 디바이스로의 출력을 위해 제공하는 단계를 더 포함할 수 있다. 하나 이상의 한지 문자 노드를 찾기 위해 찾은 병음 음절 노드를 사용하는 단계는, 찾은 병음 음절 노드의 식별자를 선택하는 단계; 및 식별자에 연관된 병음 음절 그래프에서 제1 한지 문자 노드를 찾는 단계를 포함한다. 병음 음절 그래프는 패트리샤 트리(patricia trie)이다.

전반적으로, 본 명세서에서 설명된 주제의 다른 양태는 데이터 처리 장치; 및 데이터 저장소를 포함하는 시스템에 구현될 수 있고, 상기 데이터 저장소에는 제1 쓰기 체계로 된 문자소들의 문자소 그래프―상기 문자소 그래프는 제1 복수 노드를 포함하고, 상기 제1 복수 노드에 있는 노드 각각은 상기 제1 쓰기 체계로 된 문자소를 나타내고, 상기 제1 복수 노드의 진부분집합에 있는 노드 각각은 전체 음절에 상응하고, 상응하는 전체 음절 각각은 상기 제1 복수 노드에 있는 문자소 그래프의 상응하는 노드의 문자소들과, 상기 제1 복수 노드에 있는 상기 상응하는 노드로부터 내려온 상기 노드들로부터의 상기 문자소들을 포함함―; 및 제2 쓰기 체계로 된 형태소들의 형태소 그래프―상기 형태소 그래프는 제2 복수 노드를 포함하고, 상기 제2 복수 노드에 있는 노드 각각은 제2 쓰기 체계로 된 하나 이상의 형태소를 표현하고, 상기 제2 복수 노드의 진부분집합에 있는 노드 각각은 어휘 항목에 상응하고, 상응하는 어휘 항목 각각은 상기 제2 복수 노드에 있는 형태소 그래프의 상응하는 노드의 형태소들과 제2 복수 노드에 있는 상응하는 노드로부터 내려오는 노드들의 형태소들을 포함함―가 저장된다. 본 양태의 다른 실시예들은 상응하는 방법들, 장치, 및 컴퓨터 프로그램 제품들을 포함한다.

이러한 또는 그 밖의 실시예들은 후술되는 특징들 중 하나 이상을 선택적으로 포함할 수 있다. 데이터 저장소는 하나 이상의 어휘 항목의 조합을 점수화하는 언어 모델을 더 저장한다.

본 명세서에서 설명된 주제의 특정 실시예들은 후술하는 이점 중 하나 이상을 실현하기 위해 구현될 수 있다. 제2 쓰기 체계로 된 상응하는 어휘 항목들을 식별하기 위하여 제1 쓰기 체계로 된 입력을 분석하기 위해 문자소 그래프와 형태소 그래프를 사용함으로써 가능성 있는 어휘 항목들의 탐색 영역이 확장되고, 이로써 고려되는 후보 어휘 항목들의 개수가 증가되고 정확성과 회수(recall)가 향상된다. 이에 더하여, 제2 쓰기 체계로 된 상응하는 어휘 항목을 식별하기 위하여 제1 쓰기 체계로 된 입력을 분석하기 위해 문자소 그래프 또는 형태소 그래프를 이용함으로써 후보 어휘 항목들을 식별하기 위해 요구되는 입력의 토큰(예컨대, 문자) 개수가 감소되고, 이로써 입력 방법의 편의성과 효율성이 증가되고 사용자의 경험이 향상된다.

후보 어휘 항목들을 식별하기 위해 요구되는 입력의 토큰 개수를 감소시키는 것은 더욱 작은 키패드 또는 예측 키보드(predictive keyboard)를 구비하는 모바일 디바이스(예컨대, 모바일 폰) 상에서 특히 유용할 수 있다. 이에 더하여, 모든 입력 텍스트(예컨대, 모든 병음 입력 스트링)를 분석할 수 있는 입력 방법 편집기는 입력 텍스트를 위한 출력 후보를 제공하기 위해 요구되는 사용자 입력과 상호 작용의 양을 감소시키고, 이로써 입력 방법의 편의성과 효율성이 더욱 증가되고 사용자 경험이 더욱 향상된다. 예를 들어, 사용자는 병음 음절 각각을 입력할 필요가 없고, 병음 음절 각각을 위한 출력 후보를 별도로 선택할 필요가 없다.

본 명세서에서 설명된 주제에 대한 하나 이상의 실시예가 첨부 도면들과 후술하는 상세한 설명에서 개시된다. 본 주제에 대한 다른 특징들, 양태들, 및 장점들은 상세한 설명, 도면들, 및 청구항들로부터 명백해질 것이다.

도 1a-1f는 제1 쓰기 체계로 된 예시적 텍스트 입력과 제2 쓰기 체계로 된 예시적 출력 텍스트 후보들을 포함한다.
도 2는 텍스트 입력의 관찰 시퀀스(observed sequence)와 텍스트 입력의 관찰 시퀀스에 의해 표현되는 음절들의 잠재적 시퀀스(potential(sequence)를 예시하는 블록도이다.
도 3은 예시적 문자소 그래프를 나타낸다.
도 4는 예시적 형태소 그래프를 나타낸다.
도 5는 문자소 그래프와 형태소 그래프의 예시적 사용에 대한 단계들을 예시한다.
도 6은 제1 쓰기 체계로 된 텍스트 입력에 기초하여 제2 쓰기 체계로 된 출력 텍스트 후보들을 생성하는 예시적 시스템의 블록도이다.
도 7a는 제1 쓰기 체계로 된 텍스트 입력에 기초하여 제2 쓰기 체계로 된 출력 텍스트 후보들을 생성하는 예시적 프로세스를 나타내는 순서도이다.
도 7b는 제1 쓰기 체계로 된 텍스트 입력에 기초하여 제2 쓰기 체계로 된 출력 텍스트 후보들을 생성하는 다른 예시적 프로세스를 나타내는 순서도이다.
도 8은 본 명세서에서 설명된 시스템들과 방법들을 구현하기 위해 이용될 수 있는 예시적 시스템의 블록도이다.
도 9는 예시적 입력 방법 편집기의 블록도이다.
여러 도면에서 유사한 참조 번호와 명칭들은 유사한 구성요소들을 가리킨다.

개요( overview )

도 1a-1f는 제1 쓰기 체계로 된 예시적 텍스트 입력과 제2 쓰기 체계로 된 예시적 출력 텍스트 후보들을 포함한다. 도 1a-1f는 제1 쓰기 체계(예컨대, 병음)로 된 예시적 텍스트 입력을 포함한다. 도 1c, 1d, 및 1f는 또한 제2 쓰기 체계(예컨대, 한지)로 된 예시적 출력 텍스트 후보들을 포함한다. 도 1a-1f에 포함된 예시적 텍스트 입력과 예시적 출력 텍스트 후보들은 일부 로마자와 한지 문자들 간에 구획 문자들(예컨대, 스페이스들)을 포함한다. 이러한 구획 문자들의 포함은 이 예들을 더 쉽게 이해할 수 있게 하고, 구획 문자들이 실제로는(예를 들어, 로마자를 입력하는 동안) 포함되지 않을 수도 있고, 사용자가 스페이스들을 사용하여 로마자를 분리하지 않을 수도 있다.

예로서, 사용자는 입력 방법 편집기(IME)에 로마자를 입력함으로써, 중국어 문장

(예컨대, 영어로는 "we are going to America")을 입력하고 싶어할 수 있다. 사용자에 의해 입력된 입력 로마자는 제1 쓰기 체계인 병음으로 표현되기 위해 사용될 수 있다. 사용자는 IME가 제2 쓰기 체계인 한지로 된 출력을 제공하기를 원할 수 있다. 중국어 문장

의 전체 병음 표현(full Pinyin representation)은

이 된다. 사용자가 전체 병음 표현을 예를 들어, 특히 모바일 디바이스(예컨대, 모바일 폰) 상에서 입력하는 것은 불편할 수 있다.

따라서, 사용자는 전체 병음 표현보다 적은 캐릭터의 개수(예컨대, 축약)를 입력하고 싶어할 수 있다. 도 1a는 로마자 "w", m", "q", "m", 및 "g"를 포함하는 예시적 입력 텍스트를 나타낸다. 도 1a에 도시된 예시적 입력 텍스트에 상응하는 잠재적 한지 문자들을 식별하기 위해서, 입력 방법 편집기는 예시적 입력 텍스트를 잠재적 전체 병음 표현에 매핑할 수 있다. 이상적으로는, 입력 방법 편집기가 예시적 입력 텍스트 "w m q m g"를 전체 병음 표현

에 매핑할 수 있다.

전체 병음 표현을 식별하는 작업은 2가지 원초적 문제점을 나타낸다. 도 1a-1d, 및 1f에 도시된 바와 같이, 로마자를 병음 음절로 분리하는 것이 공지되어 있다고 가정하면, 한가지 문제는 사용자가 의도했던 병음 음절을 로마자의 분리된 그룹이 표현하는지 판단하는 것이다. 이 문제는 도 1b-d를 참조하여 예시될 수 있다. 도 1b는 로마자 "w", "o", "m", "q", "u", "m", "e", "i", "g", "u", "o"를 포함하는 예시적 입력 텍스트를 나타낸다. 도 1b에 도시된 예시적 입력 텍스트

가 도 1a에 도시된 것보다 전체 병음 표현

에 매치하는 더 많은 문자들(유효한)을 포함하지만,

는 도 1c와 1d에 도시된 바와 같이 두 개 이상의 전체 병음 표현을 여전히 표현할 수 있다.

도 1c는 중국어 문장

에 대한 전체 병음 표현을 나타내고, 도 1d는 중국어 문장

(예컨대, 영어로는 "I've never went to America")에 대한 전체 병음 표현을 나타낸다. 도 1c와 1d에서, "wo"는 "我"에 상응하고, "qu"는 "去"에 상응하고, "mei"는 "美"에 상응하고, 및 "guo"는 "國"에 상응한다. 도 1c와 1d는 사용자가 문자 "m"의 최초 출현(문자 "wo" 이후에)이 "們"에 상응할 수 있는 병음 음절 "men" 또는 "沒"에 상응할수 있는 병음 음절 "mei" 중 하나를 표현하고자 했을 수 있다는 것을 예시하기 위해 사용될 수 있다.

또 다른 문제는 각 로마자 입력이 다른 병음 음절(또는 한지 문자)를 표현하는지 여부를 판단하는 것이다. 상술한 것처럼, 각 병음 음절(예컨대, 전체 병음 음절)은 한지 문자에 상응한다. 이 문제는 도 1d-1f를 사용하여 예시될 수 있다. 다시, 도 1d가 예시적 입력 텍스트가 분할(예컨대, "wo", "mei", "qu", "mei", "guo" 각각이 병음 음절을 표현함)된다고 가정한다. 도 1e는 분할되지는 않았다는 것을 제외하고, 도 1d에 도시된 것과 동일한 예시적 입력 텍스트의 시퀀스를 나타낸다.

도 1e에 도시된 예시적 입력 텍스트"w o m e i q u m e i g u o"는 도 1d에 도시된 것과 같은 병음 음절들의 시퀀스 또는 도 1f에 도시된 병음 음절들의 시퀀스를 표현할 수 있다. 특히, 문자 "g", "u", "o"의 시퀀스는 도 1d에 도시된 바와 같이 단일 병음 음절 "guo"를 표현할 수 있다. 두 번째 예시에서, "gu"가 제1 병음 음절을 나타내고, "o"가 제2 병음 음절을 나타낼 수 있다. 도 1f는 사용자가 문장

(예컨대, 영어로는 ""My younger sister will go to Plun Valley")를 입력하고자 했을 수 있다는 것을 나타낸다. 또한, 도 1f는 "mei"가 예컨대, "妹"와 "梅" 같이 다른 한지 문자들에 상응할 수 있다는 것을 나타낸다.

도 2는 텍스트 입력의 관찰 시퀀스와, 텍스트 입력의 관찰 시퀀스에 의해 표현되는 음절들의 잠재적 시퀀스들(예를 들어, 은닉 마크코프 모델(hidden markov model)로 된 은닉 시퀀스들)을 예시한 블록도(200)이다. 특히, 도 2는 도 1c와 1d에서 예시된 음절들의 잠재적 시퀀스들을 나타낸다. 텍스트 입력 "w m q m g"의 관찰 시퀀스는 "wo men qu mei guo" 또는 "wo mei qu mei guo" 중 하나로 표현할 수 있다. 음절들의 다른 잠재적 시퀀스들도 가능하다(도시되지 않음). 예를 들어, 도 1f를 참조하여 예시된 것처럼, 텍스트 입력 "w m q m g"의 관찰 시퀀스는 "wo mei qu mei gu o"로도 표현될 수 있다.

제1 쓰기 체계(예컨대, 병음)로 된 텍스트 입력이 수신되었을 때, 상술되어진 2가지 원초적 문제는 (ⅰ) 제1 쓰기 체계로 된 텍스트 입력에 기초하여 제1 쓰기 체계로 된 n-그램 표현(예컨대, 병음 음절들)을 식별하고, (ⅱ) 식별된 n-그램 표현에 기초하여 제2 쓰기 체계로 된 어휘 항목들(예컨대, 한지 용어들)과 형태소들(예컨대, 한지 문자들)을 식별함으로써 해결될 수 있다. 이상적으로는, 사용자의 희망하는 입력으로 표현될 가능성이 가장 높은 형태소들이 식별된다.

예시적 문자소 그래프( Example Grapheme Graph )

문자소 그래프가 제1 쓰기 체계로 된 입력 텍스트로 표현된 제1 쓰기 체계로 된 n-그램 표현들을 식별하는데 사용될 수 있다.

n-그램은 n개의 연속하는 토큰들(예컨대, 문자들 또는 단어들)의 시퀀스이다. n-그램은 n-그램에 있는 토큰들의 개수인 체제(order)를 갖는다. 예를 들어, 1-그램(또는 유니그램)은 한 개의 토큰을 포함하고, 2-그램(또는 바이-그램)은 두 개의 토큰을 포함한다. 예로서, "wo"는 제2 쓰기 체계로 된 형태소(예컨대,

로 발음되는 "我",

로 발음되는 "臥")에 대한 제1 쓰기 체계(예컨대, 병음 음절)로 된 2-그램 표현일 수 있다. 다른 예시로서, "m"은 제2 쓰기 체계로 된 형태소(예컨대, "men"으로 발음되는 "們",

로 발음되는 "沒")에 대한 제1 쓰기 체계로 된 1-그램 표현일 수 있다. 이 예시들에서, 제1 쓰기 체계는 병음이고, 제2 쓰기 체계는 한지이다.

도 1c에 도시된 예시로 잠시 돌아와서, 중국어 문장

은 유니그램[예를 들어, 단어 "我們"(예컨대, 영어로는 "we"), "去"(예컨대, 영어로는 "went"), 및 "美國"(예컨대, 영어로는 "America")]으로 분할될 수 있다. 예시적 바이-그램은 "我們, 去"와 "去, 美國"이 있다. 이 예시에서, 바이-그램에 있는 토큰들은 콤마로 분할된다.

도 3은 문자소 그래프(300)를 나타낸다. 특히, 문자소 그래프(300, 예컨대 병음 입력 그래프)는 예를 들어 루트 노드(302)와 하나 이상의 자식 노드(child node)들과 같은 하나 이상의 노드(예컨대, 병음 음절 노드들)를 포함하는 트리(trie)이다. 루트 노트를 제외하고, 노드 각각은 제1 쓰기 체계(예를 들어, 병음)로 된 문자소(예를 들어, 로마자)를 표현한다. 노드들은 레벨들로 분류될 수 있다. 예를 들어, 루트 레벨은 루트 노드(302)를 포함할 수 있다. 제1 레벨은 루트 노드(302)에 대한 직계 자식 노드들(direct child nodes; 예컨대, 노드(310, 312, 314))을 포함할 수 있다. 제1 레벨에 있는 노드(301, 312, 314) 각각은 제1 서브-음절(예를 들어, 프리픽스)인 문자소를 표현한다. 예를 들어, 노드들(310, 312, 314)은 병음 음절을 시작하는 제1 로마자를 표현한다. 문자소 그래프(300)는 제2 쓰기 체계(예컨대, 한지 문자)로 된 형태소에 대한 제1 쓰기 체계(예컨대, 병음 음절)로 된 n-그램 표현들을 식별하기 위하여 루트 노드(302)로부터 그 노드의 자식 노드들까지 이동될 수 있다.

또한, 문자소 그래프(300)에 있는 노드 각각은 문자소 그래프의 상응하는 노드의 문자소들과 그 상응하는 노드로부터 내려온 노드들의 문자소들을 포함하는 n-그램 표현들에 상응한다. 예를 들어, 노드(310)은 n-그램 표현 "a"에 상응한다. 노드(324)는 n-그램 표현 "be"에 상응하고, 노드(330)는 n-그램 표현 "ang"에 상응한다.

이외에도, 문자소 그래프(300)에 있는 노드들의 진부분집합은 제2 쓰기 체계로 된 형태소에 상응하는 전체 음절(예컨대, 병음 음절)에 상응한다. 특히, 노드(310, "a"), 노드(320, "ai"), 노드(321, "an"), 노드(322, "ao"), 노드(323, "ba"), 노드(325, "zu"), 및 노드(330, "ang")는 전체 음절에 상응한다. 이 진부분집합은 문숫자(shaded node)들로 문자소 그래프(300)의 시각적 표현들로 지시된다. 대안적으로, 빗금쳐지지 않은 노드들은 음절의 일부에만 상응한다. 예를 들어, 노드(312, "b"), 노드(314, "z"), 노드(324, "be")는 병음 음절의 일부(예를 들어, 서브-음절)에만 상응한다. 빗금쳐지지 않은 노드들이 병음 음절의 일부에만 상응하기 때문에, 그 노드들은 제2 쓰기 체계에 있는 형태소에 상응하지 않는다.

노드들(예를 들어, 빗금쳐진 노드들)의 진부분집합에 있는 노드 각각도 식별자에 연관된다. 예를 들어, 노드(310)는 식별자 "1"에 연관되고, 노드(320)는 식별자 "2"에 연관되고, 노드(321)은 식별자 "3"에 연관되고, 노드(322)는 식별자 "5"에 연관되고, 노드(323)는 식별자 "6"에 연관되고, 노드(325)는 식별자 "418"에 연관되고, 노드(330)는 식별자 "4"에 연관된다. 식별자들은 문자들의 임의 다른 조합들(예컨대, 문자와 숫자가 합쳐진(alphanumeric) 스트링) 또는 숫자들일 수 있다.

보다 상세하게 후술될 것처럼, 식별자 각각은 형태소 그래프에서 노드들을 찾기 위하여 사용될 수 있다. 도 4를 잠시 참조하면, 간단한 개요로서, 형태소 그래프(400)는 제2 쓰기 체계(예컨대, 한지 문자들)로 된 하나 이상의 형태소에 각각 상응하는 노드들을 포함한다. 형태소 그래프(400)에 있는 하나 이상의 진부분집합은 제2 쓰기 체계(예컨대, 한지 용어들)로 된 어휘 항목들에 상응한다. 문자소 그래프(300)로부터 선택된 식별자는 예를 들어, 형태소 그래프(400)에서 그 식별자에 연관된 노드들을 찾음으로써 형태소 그래프(400)를 이동하기 위해 사용될 수 있다. 예를 들어, 노드(401)도 식별자 "1"에 연관되고, 노드(412)도 식별자 "2"에 연관되고, 노드(414)도 식별자 "3"에 연관되고, 노드(416)도 식별자 "418"에 연관된다. 도 4에서, 식별자들은 제1 레벨에 있는 노드들에 대해서만 예시되었지만, 실제로 식별자는 각 빗금쳐진 노드들에 연관된다.

도 3으로 돌아가서, 각 문자소(예컨대, 로마자)가 입력 방법 편집기에 의해 수신되기 때문에, 문자소 그래프(300)는 제1 쓰기 체계로 된 가능성 있는 n-그램 표현들을 식별하는데 사용될 수 있다. 예를 들어, 로마자 "b"가 수신되면, 노드(312)가 찾아질 수 있다. 다른 예시에서, 로마자 "a"가 "b" 이후에 수신될 수 있다. 다시 말하면, 입력 시퀀스가 "ba"일 수 있다. 따라서 노드(323)가 "ba"를 위해 찾아질 수 있고, 노드(310, 320, 321, 322, 330)가 "a"로 시작하는 나머지 병음 음절을 위해 찾아질 수 있다. 특히, 입력 시퀀스 "ba"는 병음 음절 "ba", "ba"로 시작하는 병음 음절, 또는 "b"로 시작하는 병음 음절과 "a"로 시작하는 병음 음절을 표현할 수 있다.

다른 구현예들에서, 가능성 있는 n-그램 표현들이 입력 시퀀스로 표현된 빗금쳐진 노드들을 찾음으로써 식별된 후에, 찾아진 빗금쳐진 노드들에 대한 연관된 식별자들이 반환될 수 있다. 상술된 바와 같이, 이러한 식별자들이 어휘 항목들을 식별하기 위하여 형태소 그래프에서 노드들을 찾기 위해 사용될 수 있다.

다른 구현예들도 가능하다. 예를 들어, 문자소 그래프(300)는 패트리샤 트리(Patricie trie)이지만, 문자소 그래프(300)는 다른 형태의 데이터 구조들(예컨대, 해쉬 테이블, 균형 트리(balanced trie))로 구현될 수 있다. 이외에도, 일부 구현예들에서, n-그램 표현들이 식별자들을 대신해서 또는 식별자들의 조합으로 반환될 수 있다. 또한, 문자소 그래프(300)는 쓰기 체계의 다른 조합들을 표현하도록 구현될 수도 있다. 예를 들어, 제1 쓰기 체계는 보포모포(bopompfo)일 수 있고, 제2 쓰기 체계는 한지일 수 있다. 다른 예시로서, 제1 쓰기 체계는 로마지(Romaji, 예컨대, 일본어의 로마자체)이고, 제2 쓰기 체계는 간지-일본어(Kanji-Japanese)일 수 있다.

예시적 형태소 그래프( Example Morpheme Graph )

도 4는 형태소 그래프(400)를 나타낸다. 특히, 형태소 그래프(400, 예컨대 병음 음절 그래프)는 예를 들면, 루트 노드(402)와 하나 이상의 자식 노드와 같은 하나 이상의 노드들(예를 들어, 한지 문자 노드들)을 포함하는 트리이다. 노드들은 레벨들로 분류될 수 있다. 예를 들어, 루트 레벨은 루트 노드(402)를 포함할 수 있다. 제1 레벨은 루트 노드(402)의 직계 자식 노드들(예컨대, 노드(410, 412, 414, 416)를 포함할 수 있다. 제1 레벨에 있는 노드들(410, 412, 414, 및 416)은 어휘 항목의 프리픽스를 표현한다. 예를 들어, 제1 레벨에 있는 노드들(410, 412, 414, 416)은 한지 용어(예를 들어, 단어 또는 구)로 시작하는 제1 한지 문자를 표현할 수 있다. 형태소 그래프(400)는 문자소 그래프(300)을 사용하여 식별된 n-그램 표현들에 기초하여 제2 쓰기 체계로 된 어휘 항목을 식별하기 위하여 루트 노드(402)에서부터 자식 노드들까지 이동될 수 있다.

형태소 그래프(400)에 있는 노드 각각은 제2 쓰기 체계로 된 하나 이상의 형태소를 표현한다. 예를 들어, 노드(410)는 형태소들 "阿", "呵", 및

를 표현할 수 있고, 각 형태소는 여러가지 형태(예컨대,

)로 발음될 수 있다. 다른 예시로서, 노드(421)는 "屋"(도시되지 않음)을 표현할 수 있다. 이외에도, 형태소 그래프(400)에 있는 노드들의 진부분집합은 어휘 항목들(예컨대, 한지 용어들)에 상응한다. 예를 들어, 노드들(410, 412, 414, 416, 420, 422, 423, 424, 425, 440)은 어휘 항목들에 상응한다. 이 진부분집합은 빗금쳐진 노드들로서 형태소 그래프(400)의 시각적 표현으로 제시된다. 대안적으로, 빗금쳐지지 않은 노드들은 어휘 항목의 일부에만 상응한다. 예를 들어, 노드들(421, 430)은 어휘 항목의 일부에만 상응한다. 특히, 노드(421)는 단지 어휘 항목의 일부(예컨대, 노드(440)에 상응하는 중국어 관용구

의 일부)인 "愛屋"에 상응할 수 있다.

상응하는 어휘 항목 각각은 형태소 그래프의 상응하는 노드의 형태소들과, 그 상응하는 노드로부터 내려온 노드들의 형태소를 포함한다. 예를 들어, 노드(420)는 노드(410)로부터 내려온다. 노드(420)는 어휘 항목들

와

에 상응한다. "姨"와 "以"는 병음 음절 "yi"에 상응하는 형태소이고, "阿"는 노드(410)에 상응하는 형태소이다.

형태소 그래프(400)에 있는 노드들이 제1 쓰기 체계로 된 n-그램 표현들로 명명(예컨대, 노드(410)은 "a"로 명명되고, 노드(430)는 "ji"로 명명됨)되었지만, 실제로 노드들은 식별자들에 연관된다(예컨대, 문자소 그래프(300)로부터의 식별자와 동일함). 예를 들어, 상술되어진 바와 같이, 노드(410)는 식별자 "1"에 연관되고, 노드(416)는 식별자 "418"에 연관된다. 이외에도, 형태소 그래프에 있는 노드들도 상응하는 어휘 항목들을 식별하는 어휘 항목 식별자들(예컨대, 노드(425)에서 "足部"에 대한 "32778")에 연관될 수 있다.

일부 구현예들에서, 어휘 항목들(예컨대, 한지 용어들)은 형태소 그래프(400)와 분리된 데이터 구조로 저장된다. 이러한 또는 그 밖의 실시예들에서, 형태소 그래프의 각 노드는 문자소 그래프로부터의 식별자와 어휘 항목 식별자들에 오직 연관될 수 있다. 예를 들어, 어휘 항목들은 어휘 항목 식별자들로 인덱스된 사전에 저장될 수 있다. 형태소 그래프에서 찾은 노드들(예컨대, 빗금쳐진 노드들)은 사전에 있는 어휘 항목들을 식별하기 위해 사용될 수 있는 어휘 항목 식별자들을 제공한다.

도 5에 도시된 바와 같이, 문자소 그래프(300)를 사용하여 식별된 제1 쓰기 체계로 된 입력 시퀀스들의 n-그램 표현들에 대한 순열(permutation)들은 가능성 있는 어휘 항목들을 식별하기 위하여 형태소 그래프를 이동하는데 사용된다.

도 5는 문자소 그래프와 형태소 그래프의 예시적 사용에 대한 단계를 예시한다. 단계 0에서, 입력이 수신되지 않고, 문자소 그래프와 형태소 그래프에서는 자식 노드들을 찾을 수 없었다.

단계 1에서, 로마자 "w"가 입력 방법 편집기에 의해 수신된다. 응답으로서, 입력 방법 편집기는 문자소 그래프의 제1 레벨에서 "w"로 표현되는 노드를 찾는다. 또한 입력 방법 편집기는 "w"로 표현되는 노드로부터 내려오고, 전체 음절에 상응(예컨대, 제2 쓰기 체계로 된 형태소에 상응함)하는 문자소 그래프에 있는 노드들의 진부분집합에서 모든 노드들을 찾는다. 찾은 노드들에 연관된 식별자들은 한지 문자들로 표현되는 형태소 그래프에서 노드들을 찾기 위해 사용될 수 있다. 예를 들어, "w"는 병음 음절들 "wu", "wo", 및 "wei"의 제1 서브-음절이다. 도 5에 도시된 단계 1을 참조하면, "无"는

에 상응하고, "我"는

에 상응하고,

는

에 상응한다. 단계 1에서, 예시로서 "w"에 대해 가장 가능성이 높은 후보들일 수 있는 3개의 병음 문자(예컨대, "无", "我", 및

)만이 도시되어 있다. 마찬가지로, 단계 2는 로마자 "w"와 "o"의 수신에 응답하여 처리된 가능성 있는 후보들의 일부만을 나타낸다. 도 5는 실제로 처리된 모든 가능성 있는 후보들을 나타내고 있지는 않다.

단계 2에서, 로마자 "o"는 로마자 "w"가 수신된 후에 입력 방법 편집기에 의해 수신된다. 문자소 그래프의 제1 레벨에서 "w"를 표현하는 노드를 찾는 것 이외에, 입력 방법 편집기는 또한 문자소 그래프의 제1 레벨에서 "o"를 표현하는 노드를 찾는다. 상술된 바와 같이, "w"가 전체 병음 음절의 제1 서브-음절이거나, "o"가 전체 병음 음절의 제1 서브-음절이거나, 또는 "wo"가 전체 병음 음절일 수 있다. 입력 방법 편집기는 또한 전체 병음 음절에 상응하는 문자소 그래프에 있는 노드들의 진부분집합에서 "w"와 "o"를 표현하는 노드로부터 내려온 모든 노드들을 찾는다. 찾은 노드들과 연관된 식별자들이 전체 음절을 표현하는 한지 문자들을 표현하는 형태소 그래프에서 노드들을 찾기 위해 사용될 수 있다. 예를 들어, "w"는 병음 음절 "wo"의 제1 서브-음절이다. 도 5에 도시된 단계 2를 참조하면, "我"는

에 상응하고,

는

에 상응한다. 다른 예시로서, "o"는

에 상응하는

인 전체 병음 음절이다.

점수 부여( scoring )

상술된 바와 같이, 입력 텍스트로 표현되는 어휘 항목들의 가능성 있는 순열들은 문자소 그래프와 형태소 그래프를 사용하여 식별된다. 예를 들면, 도 5로 돌아가서, 단계 1은 로마자 "w"로 표현될 수 있는 제1 어휘 항목들 "无", "我", 및

를 나타낸다. 제1 문자소(예컨대, "w")만을 수신한 후, 제1 어휘 항목들 예를 들어 "无", "我", 및

중 하나가, 제1 용어 항목들 각각에 연관된 점수에 기초하여 선택될 수 있다. 예를 들어, 존재할 가능성이 가장 높은 용어 항목이 선택(및 디스플레이)될 수 있다.

상술된 것처럼, 추가 문자소들이 입력(예컨대, 제2 문자소)으로서 수신되면, 제1 문자소와 제2 문자소가 하나 이상의 제1 어휘 항목을 표현하거나, 또는 제1 문자소와 제2 문자소가 다른 문자 용어를 각각 표현(예컨대, 제2 문자소는 하나 이상의 제2 어휘 항목의 그룹으로부터 하나의 어휘 항목을 표현함)할 수 있다. 이러한 경우들을 설명하기 위하여, 제3 어휘 항목들과 제4 어휘 항목들로 된 순열들이 생성되고 점수가 부여될 수 있다. 제3 어휘 항목들은 하나 이상의 제1 어휘 항목으로부터 선택될 수 있고, 제4 어휘 항목들은 하나 이상의 제2 어휘 항목들로부터 선택될 수 있다. 제1 어휘 항목들의 점수와 순열들의 점수가 가장 가능성 있는 어휘 항목을 제공하기 위해 비교될 수 있다.

예를 들어, 도 5에서, 제1 어휘 항목들

,

, 및

에 대한 점수들이 식별되거나, 또는 산출될 수 있다. 이외에도, 순열들

,

, 및

의 점수가 식별될 수 있다. 다시, 이 예시는 실제로 처리될 모든 가능성 있는 제1 어휘 항목들과 순열들을 예시하지는 않았다. 식별된 점수들은 예를 들어, 디스플레이를 위하여 가장 높은 점수를 갖는 어휘 항목 또는 순열을 제공하기 위하여 비교될 수 있다.

일부 구현예들에서, 가능성 있는 순열들이, 그 순열들이 존재할 가능성을 산출하기 위하여 n-그램 언어 모델에 송신되고, 하나 이상의 순열이 하나 이상의 기준(ctiteria)에 기초하여 선택될 수 있다. 예를 들어, 일어날 가능성이 가장 높은 순열이 선택될 수 있다.

n-그램 언어 모델에 따른, 특정 스트링(예컨대, 어휘 항목들의 순열)이 일어날 가능성은 체인 규칙(chain rule)을 사용하여 결정될 수 있다. 체인 규칙은 개별적 가능성들의 곱으로서 스트링의 확률을 결정한다. 따라서, 주어진 스트링 "e₁, e₂, …, e_k"의 경우, 스트링에 대한 확률, p(e₁, e₂, …, e_k)는 아래 식과 같다.

n-그램 언어 모델은 특정 최대 크기 n-그램으로 제한(예컨대, 1-그램, 2-그램, 3-그램 등으로 제한)될 수 있다. 예를 들어, 특정 스트링 "NASA officials say they hope"의 경우, 최대 n-그램 체제(maximum n-gram order)가 3-그램으로 제한되면, 그 스트링에 대한 확률은 아래와 같이 조건부 확률의 곱으로서 결정될 수 있다. p(NASA officials say they hope)=p(NASA)·p(officials｜NASA)·p(say｜NASA officials)·p(they｜officials say)·p(hope｜say they). 이는 아래 식으로 일반화될 수 있다.

여기서, n은 언어 모델에서 허용된 최대 n-그램의 체제이다.

조건부 확률들은 훈련 데이터의 문서들에 있는 상관 빈도들(relative frequencies)에 따라서, 일반적으로 실험에 의해 결정된다. 예를 들어, 상기 예시에서, 주어진 콘텐츠 "NASA officials"에 대한 "say"의 가능성은 아래 식에 의해 얻어진다.

여기서 f(NASA officials say)는 훈련 데이터의 문서에서 스트링 "NASA officials say"의 존재에 대한 빈도, 즉 총수이다. n-그램 언어 모델에 있는 최대 n-그램 체제 내에 스트링들에 대한 조건부 확률들은 n-그램을 위하여 언어 모델에 저장된 확률에 상응하고, 예를 들어 p(say｜NASA officials)는 3-그램 입력 "NASA officials say"을 위하여 언어 모델에 저장된 조건부 확률이다.

마찬가지로, 조건부 확률들은 다른 쓰기 체계를 위해 산출될 수 있다. 도 1c에 도시된 예시로 잠시 돌아가면, p(去｜我們)는 2-그램 입력 "我們, 去"를 위하여 언어 모델에 저장된 조건부 확률이고, p(美國｜我們, 去)는 3-그램 입력 "我們, 去, 美國"을 위하여 언어 모델에 저장된 조건부 확률이다.

일부 구현예들에서, 순열들 각각의 점수가 비교되고, 일어날 가능성이 가장 높은 순열이 사용자(예컨대, 사용자 디바이스 상에)에게 제시된다. 일부 구현예들에서는, 사용자에게 제시된 순열이 옳지 않으면, 사용자가 제시된 순열의 선두로부터 올바른 형태소를 식별(예컨대, 선택)할 수 있고, 입력 방법 편집기는 디스플레이를 위해 다른 순열을 생성할 수 있다. 예를 들어, 도 1b-1d로 돌아가서, 사용자는 입력으로서 "wo m qu mei guo"를 제공할 수 있다. 입력 방법 편집기는 가장 가능성 있는 순열로서 "我們去美國"를 디스플레이할 수 있다. 그러나 사용자는 "我沒去美國"을 입력하려고 했을 수 있다. 사용자는 "我"만을 선택할 수 있다. 응답으로, 입력 방법 편집기는 문자소 그래프와 형태소 그래프에 있는 "wo"로부터 식별된 "我"를 판단할 수 있고, 불완전한 스트링 "m qu mei guo"에 기초하여 문자소 그래프와 형태소 그래프를 사용하여 이전에 식별된 추가 후보들을 디스플레이할 수 있다. 예를 들어, 입력 방법 편집기는 "沒去美國"(예컨대, 영어로는 "never went to America")와

(예컨대, 영어로는 "mother is going to America")를 디스플레이할 수 있다.

는 병음 음절

에 상응한다. 다른 구현들들도 가능하다. 예를 들어, 사용자는 제시된 순열의 임의의 형태소를 올바른 것으로 식별할 수 있다.

예시적 시스템( Example System )

도 6은 제1 쓰기 체계로 된 텍스트 입력에 기초하여 제2 쓰기 체계로 된 출력 텍스트 후보들을 생성하는 예시적 시스템(600)의 블록도이다. 시스템(600)은 오프라인 생성 모델(610)을 포함한다. 오프라인 생성 모델(610)은 훈련 데이터(도시되지 않음)로부터 사전(612)을 생성할 수 있다. 훈련 데이터의 예로서 웹 페이지들, 인스턴스 메시지 로그들, 뉴스, 및 텍스트의 다른 소스들이 포함될 수 있다. 사전(612)은 병음 음절에 연관되고, 점수(예컨대, 훈련 데이터에서 일어나는 한지 문자들의 빈도)에 연관된 한지 문자들을 포함할 수 있다. 사전(612)은 병음 음절과 연관된 점수들을 포함하는 병음 테이블(614)을 생성하기 위해서 분석될 수 있다. 사전(612)은 병음 음절들, 연관된 한지 문자들, 및 각각의 식별자들을 포함하는 사전 모델(620)을 생성하기 위하여, 사전 구축기(616)에 의해 사전(612)이 분석되고, 병음 트리 구축기(618)에 의해 병음 테이블(614)이 분석될 수 있다.

사전 모델(620)은 사전 트리(632, 예컨대 형태소 그래프(400))와 병음 트리(634, 예컨대 문자소 그래프(300))를 생성하기 위해 IME(630)에 의해 사용될 수 있다. 입력(640, 예컨대 사용자 입력)이 수신되면, 병음 분석기(636)와 사전 분석기(638)가 상술한 도 1 내지 도 5를 참조하여 설명한 것처럼, 사전 트리(632)와 병음 트리(634)를 사용하여 입력을 처리할 수 있다. IME(630)는 가장 가능성 있는 어휘 항목들의 순열을 식별하기 위하여 언어 모델(639)을 사용하고, 사용자 디바이스 상에 디스플레이를 위해, 가장 가능성 높은 순열을 출력(650)으로서 제공할 수 있다.

시스템(600)의 구성 요소들은 서로 하나 이상 통신적으로 결합될 수 있다. 상기에서 식별된 구성요소들이 독립적 또는 별개로서 설명되었지만, 그 구성요소 중 하나 이상이 단일 프로세스 또는 루틴에 결합될 수 있다. 본 명세서에서 제공되는, 개별 기능들에 대한 책임을 분리한 기능적 설명들은 예시적이다. 필요에 의해서 또는 설계 선호도에 따라서, 기능적 책임에 대한 다른 그룹핑 또는 다른 분할이 이루어질 수 있다. 예를 들어, 단일 분석기가 병음 분석기(636)과 사전 분석기(638)의 기능을 수행할 수 있다. 다른 예시로서, 사전 트리(632), 병음 트리(634), 및 언어 모델(639)이 IME(예를 들어, 도 9에 도시된 바와 같이)와 별개일 수 있다.

예시적 프로세스들( Example Prosesses )

도 7a는 제1 쓰기 체계로 된 텍스트 입력에 기초하여 제2 쓰기 체계로 된 출력 텍스트 후보들을 생성하는 예시적 프로세스(700a)를 나타내는 순서도이다. 프로세스(700a)는 제1 쓰기 체계로 된 제1 문자소를 수신하는 단계(705)를 포함한다. 예를 들어, IME(630)은 제1 문자소(예컨대, 입력(640))를 수신할 수 있다.

또한, 프로세스(700a)는 제2 쓰기 체계로 된 제1 형태소에 대한 제1 쓰기 체계에서의 제1 n-그램 표현을 식별하기 위해 제1 쓰기 체계로 된 문자소들의 문자소 그래프를 사용하는 단계(710)를 포함한다. 제1 n-그램 표현은 제1 문자소를 포함한다. 예를 들어, 병음 분석기(636)는 제2 쓰기 체계(예컨대, 한지 문자)로 된 제1 형태소에 대한 제1 쓰기 체계(예컨대, 병음 음절)에서의 제1 n-그램 표현을 식별하기 위하여 문자소 그래프(예컨대, 병음 트리(634))를 사용할 수 있다. 또한, 프로세스(700a)는 형태소 그래프에서 하나 이상의 제1 노드를 찾기 위하여 제1 n-그램 표현을 사용하는 단계(715)를 포함할 수 있다. 형태소 그래프에서 찾은 제1 노드 각각은 제2 쓰기 체계로 된 하나 이상의 제1 어휘 항목을 표현하고, 하나 이상의 제1 어휘 항목은 제1 n-그램 표현으로 표현된다. 예를 들면, 사전 분석기(638)는 형태소 그래프(예컨대, 사전 트리(632))에서 하나 이상의 제1 노드를 찾기 위해 제1 n-그램 표현을 사용할 수 있다.

또한 프로세스(700a)는 하나 이상의 제1 어휘 항목 각각에 연관된 제1 점수에 기초하여 하나 이상의 제1 어휘 항목들로부터 하나의 제1 어휘 항목을 선택하는 단계(720)를 포함한다. 예를 들어, 사전 분석기(638)는 하나 이상의 제1 어휘 항목 각각에 연관(언어 모델(639)을 사용하여 식별됨)된 제1 점수에 기초하여 제1 어휘 항목을 선택할 수 있다.

프로세스(700a)는 또한 제1 어휘 항목을 사용자 디바이스 상에 디스플레이를 위하여 제공하는 단계(725)를 포함한다. 예를 들어, IME(630)가 사용자 디바이스(예컨대, 모바일 폰) 상에 디스플레이를 위하여 제1 어휘 항목을 제공할 수 있다.

도 7b는 제1 쓰기 체계로 된 텍스트 입력에 기초하여 제2 쓰기 체계로 된 출력 텍스트 후보들을 생성하는 다른 예시적 프로세스(700b)를 나타내는 순서도이다. 일부 구현예들에서는, 프로세서(700b)가 프로세스(700a) 이후에 수행될 수 있다.

프로세스(700b)는 제1 쓰기 체계로 된 제2 문자소를 수신하는 단계(730)를 포함한다. 예를 들어, IME(630)은 제2 문자소(예컨대, 입력(640))를 수신할 수 있다. 또한, 프로세스(700b)는 제2 쓰기 체계로 된 제2 형태소에 대한 제1 쓰기 체계에서의 제2 n-그램 표현을 식별하기 위해 제1 쓰기 체계로 된 문자소들의 문자소 그래프를 사용하는 단계(735)를 포함한다. 제2 n-그램 표현은 제2 문자소를 포함한다. 예를 들어, 병음 분석기(636)는 제1 쓰기 체계에서의 제2 n-그램 표현을 식별하기 위하여 문자소 그래프(예컨대, 병음 트리(634))를 사용할 수 있다.

또한 프로세스(700b)는 형태소 그래프에서 하나 이상의 제2 노드를 찾기 위해 제2 n-그램 표현을 사용하는 단계(740)를 포함할 수 있다. 형태소 그래프에서 찾은 제2 노드 각각은 제2 쓰기 체계로 된 하나 이상의 제2 어휘 항목을 표현할 수 있고, 하나 이상의 제2 어휘 항목 각각은 제2 n-그램 표현으로 표현될 수 있다. 예를 들면, 사전 분석기(638)가 형태소 그래프(예컨대, 사전 트리(632))에서 하나 이상이 제2 노드를 찾기 위해 제2 n-그램 표현을 사용할 수 있다.

또한 프로세스(700b)는 하나 이상의 제1 어휘 항목으로부터의 제3 어휘 항목와 하나 이상의 제2 어휘 항목으로부터의 제4 어휘 항목으로 된 하나 이상의 순열을 생성하는 단계(745)를 포함한다. 예를 들어, 사전 분석기(638)는 하나 이상의 어휘 순열(예컨대, 한지 용어들의 순열들)을 생성할 수 있다.

또한 프로세스(700b)는 제3 어휘 항목와 제4 어휘 항목으로 된 하나 이상의 순열 각각에 연관된 제2 점수에 기초하여, 제3 어휘 항목와 제4 어휘 항목으로 된 하나 이상의 순열로부터 하나의 순열을 선택하는 단계(750)를 포함한다. 선택된 순열은 제4 어휘 항목이 이어지는 제3 어휘 항목을 포함한다.

프로세스(700b)는 또한 선택된 제1 어휘 항목의 제1 점수와 선택된 순열의 제2 점수를 비교하는 단계(755)를 포함하고, 사용자 디바이스 상에 디스플레이를 위하여, 선택된 제1 어휘 항목 또는 선택된 순열을 그 비교 결과에 기초하여, 제공하는 단계(760)를 포함한다. 예를 들어, 사전 분석기(638)가 제2 점수(예컨대, 언어 모델(639)을 사용하여 식별됨)에 기초하여 순열을 선택하고, 제1 점수와 제2 점수를 비교할 수 있다. 이외에도, IME(630)는 사용자 디바이스 상에 디스플레이를 위하여, 선택된 제1 어휘 항목 또는 선택된 순열을 그 비교 결과에 기초하여, 제공할 수 있다.

다른 예시적 시스템들( Other Example System )

도 8은 본 명세서에서 설명된 시스템들 및 방법들을 구현하기 위해 이용될 수 있는 예시적 시스템(800)의 블록도이다. 예시적 시스템(800)은 예를 들어, 컴퓨터 바이스(예컨대, 개인용 컴퓨터 디바이스) 또는 다른 전자 디바이스들(예컨대, 모바일 폰, 모바일 통신 디바이스, PDA(Personal Digital Assistant), GPS(Global Positioning System) 네이게이션 디바이스 등) 내에 구현될 수 있다.

예시적 시스템(800)은 프로세싱 디바이스(802), 제1 데이터 저장소(804), 제2 데이터 저장소(806), 입력 디바이스들(808), 출력 디바이스들(810), 및 네트워크 인터페이스(812)를 포함한다. 예를 들어, 데이터 버스와 마더보드를 포함하는 버스 시스템(814)이 구성 요소들(802, 804, 806, 808, 810, 812) 간의 데이터 통신을 확립하고 제어하기 위해 사용될 수 있다. 다른 시스템 구조들도 사용될 수 있다.

프로세싱 디바이스(802)는 예를 들어, 하나 이상의 마이크로프로세서를 포함할 수 있다. 제1 데이터 저장소(804)는 예를 들어, 랜덤 액세스 메모리 저장 디바이스(예컨대, 다이나믹 랜덤 액세스 메모리), 또는 다른 형태의 컴퓨터 판독가능 매체 메모리 디바이스를 포함할 수 있다. 제2 데이터 저장소(806)는 예를 들어, 하나 이상의 하드 드라이브, 플래시 메모리, 및/또는 판독 전용 메모리(read only memory), 또는 다른 형태의 컴퓨터 판독가능 매체 메모리 디바이스를 포함할 수 있다.

예시적 입력 디바이스들(808)은 키보드, 마우스, 스타일러스 등을 포함할 수 있고, 예시적 출력 디바이스들(810)은 디스플레이 디바이스, 오디오 디바이스 등을 포함할 수 있다. 네트워크 인터페이스(812)는 네트워크(816)와 데이터를 송수신하도록 동작가능한 예를 들어, 유선 또는 무선 네트워크 디바이스를 포함할 수 있다. 네트워크(816)는 하나 이상의 LANs(Local Area Network), 및/또는 인터넷과 같은 WAN(Wide Area Network)을 포함할 수 있다.

일부 구현예들에서, 시스템(800)은 데이터 저장소(806)와 같은 데이터 저장소로부터의 입력 방법 편집기(IME) 코드(801)를 포함할 수 있다. 입력 방법 편집기 코드(801)는, 실행되면 프로세싱 디바이스(802)로 하여금 입력 방법 편집 기능들을 수행하도록 하는 명렁어들에 의해 정의될 수 있다. 입력 방법 편집기 코드(801)는 웹 브라우저 환경에서 실행될 수 있는 예를 들어, 스크립트 명령어들(예컨대, 자바스크립트 또는 ECMA 스크립트 명령어들)과 같은 해석된(interpreted) 명령어들을 포함할 수 있다. 또한, 독립형 애플리케이션, 애플렛(applet), 플러그 인 모듈(plug-in module) 등과 같은 다른 구현예들이 이용될 수 있다.

입력 방법 편집기 코드(801)의 실행은 입력 방법 편집기 인스턴스(IMEI: input method editor instance, 803)를 생성하거나 시작시킨다. 입력 방법 편집기 인스턴스(803)는, 시스템(800)이 예를 들어, 병음을 표현하는 로마자와 같은 문자들 또는 기호들에 대한 입력들을 수신하는 동안에, 시스템(800)에서 하나 이상의 입력 방법의 처리를 가능하게 한다. 예를 들어, 사용자는 한지 용어들의 식별을 위한 병음 입력들을 입력하기 위하여, 하나 이상의 입력 디바이스[808, 예를 들어 키보드(예컨대, 로마문자용 키보드), 필기 인식 엔진과 함께 사용되는 스타일러스 등]를 사용할 수 있다. 일부 예시에서, 하나의 한지 용어는 둘 이상의 병음 입력으로 작성될 수 있다.

제1 데이터 저장소(804) 및/또는 제2 데이터 저장소(806)는 입력들의 연관성을 저장할 수 있다. 사용자 입력에 기초하여, 입력 방법 편집기 인스턴스(803)는 그 사용자 입력에 의해 표현되는 하나 이상의 후보 선택들을(예컨대, 어휘 항목의 순열들) 식별하기 위하여 데이터 저장소(804) 및/또는 데이터 저장소(806)에 있는 정보를 사용할 수 있다. 일부 구현예들에서, 둘 이상의 후보 선택이 식별되면, 후보 선택들이 출력 디바이스(810) 상에 디스플레이된다. 입력 디바이스(808)를 사용하여, 사용자는 후보 선택으로부터 예를 들어 사용자가 입력하고자 하는 한지 용어를 선택할 수 있다.

일부 구현예들에서, 시스템(800)에 있는 입력 방법 편집기 인스턴스(803)는 하나 이상의 병음 입력을 수신할 수 있고, 그 입력들을 한지 용어들로 변환할 수 있다. 입력 방법 편집기 인스턴스(803)는 예를 들어, 한지 용어들을 표현하기 위하여 키스트로크(keystroke)들로부터 수신된 병음 음절(예컨대, 로마자들)의 구성(composition)을 사용할 수 있다. 각 로마자는 예를 들어, 로마문자용 키보드에 있는 키에 상응할 수 있다. 병음 입력 방법 편집기를 사용하여, 사용자는 한지 용어의 소리를 표현하는 하나 이상의 병음 음절을 포함하는 입력들을 사용함으로써 그 힌지 용어를 입력할 수 있다. 그러나, 다른 언어와 쓰기 체계를 위한 입력 방법들도 가능할 수 있다.

일부 구현예들에서, 시스템(800)에 액세스하는 원격 컴퓨팅 시스템(818)이 또한 표의문자를 편집하기 위해 사용될 수 있다. 예를 들어, 시스템(800)은 네트워크(816)를 통해 표의문자 편집 능력을 제공하는 서버일 수 있다. 일 예시에서, 사용자는 원격 컴퓨팅 시스템(예컨대, 클라이언트 컴퓨터)를 사용하여 데이터 저장소(804) 및/또는 데이터 저장소(806)에 저장된 표의문자를 편집할 수 있다. 시스템(800)은 예를 들어, 문자를 선택하고, 네트워크 인터페이스(812)를 통해 사용자로부터 입력을 수신할 수 있다. 프로세싱 디바이스(802)는 예를 들어, 선택된 문자에 인접하는 하나 이상의 문자를 식별하고, 그 수신된 입력 및 인접하는 문자들에 기초하여 하나 이상의 후보 선택을 식별할 수 있다. 시스템(800)은 후보 선택들을 포함하는 데이터 통신을 원격 컴퓨팅 시스템에 전송할 수 있다.

도 9는 예시적 입력 방법 편집 시스템(920)의 블록도이다. 입력 방법 편집 시스템(920)는 예를 들어, 입력 방법 편집기 코드(801)과 연관된 데이터 저장소(804, 806)를 사용하여 구현될 수 있다. 입력 방법 편집기 시스템(920)은 입력 방법 편집기 엔진(922), 문자소 그래프(924; 예컨대 문자소 그래프(300)), 형태소 그래프(926; 예컨대 형태소 그래프(400)), 및 언어 모델 데이터 저장소(928)를 포함한다. 다른 저장소 구조들도 사용될 수 있다.

언어 모델 데이터 저장소(928)는 하나 이상의 언어 서브-모델(예컨대, 일본어 모델, 중국어 모델 등)을 정의할 수 있다. 각 언어 모델은 예를 들어 사용자가 입력 세트를 입력함에 있어서 사용자의 가능성 있는 의도를 결정하기 위하여 사용될 수 있는 특정 규칙 세트(예컨대, 언어 고유의 문법, 구문 세트(phrase set), 동사 등)을 정의할 수 있다. 각 언어 모델은 또한 특정 사용자의 사용자 이력(예컨대 특정 사용자가 자주 사용하는 단어 또는 문구의 사전)을 포함할 수 있다.

예를 들어, 중국어 모델은 중국어 문법 모델을 포함할 수 있다. 예를 들어, 중국어 문법 모델들은 연쇄 동사 구문 모델(serial verb constructions model), 완료 및 미완료 모델들, 및 다른 문법 모델들을 포함할 수 있다.

예를 들어, 키스트로크들의 입력에 기초하여, 일련의 병음 입력이 문자소 그래프(924)를 사용하여 식별될 수 있다. 결과적으로, 병음 입력들이 형태소 그래프(926)를 사용하여 한지 문자들을 식별하기 위하여 이용될 수 있다. 중국어 문법 모델이 중국어 문맥(context)하에서 사용자가 입력하고자 하는 의도에 대한 가능성을 판단하기 위하여 한지 문자들에 적용될 수 있다. 예를 들어, 모두 동사인 한지 문자들로 된 입력 스트링이 매우 낮은 점수를 갖지만, 동사와 목적어를 갖는 입력 스트링은 높은 점수를 가질 수 있다. 예를 들어 다른 예시에서, "나는 꽃을 사랑합니다"라고 읽는 중국어 문자로 된 입력은 높은 점수를 받고, "침대 소 TV"라고 읽는 중국어 문자로 된 입력 스트링은 낮은 점수를 받는다.

다른 프로세스들이 점수를 조정하기 위해 사용될 수 있다. 예를 들어, 특정 언어에서 자주 사용하지 않는 단어들은 더 낮게 조정될 수 있는 반면, 사용자 프로파일에 의해 정의된 것처럼, 자주 사용된 언어 또는 구문은 더 높게 조정될 수 있다. 다른 구현예들도 사용할 수 있다.

본 명세서에 기재된 주제와 기능적 동작들의 실시예들은 디지털 전자 회로로 구현되거나, 또는 상세한 설명에 기재된 구조 및 그들의 구조적 등가물을 포함하는 컴퓨터 소프트웨어, 펌웨어, 또는 하드웨어로 구현되거나, 또는 이들 중 하나 이상의 조합으로 구현될 수 있다. 본 명세서에 기재된 주제의 실시예들은 하나 이상의 컴퓨터 프로그램 제품, 즉, 데이터 프로세싱 장치(예컨대, 프로세싱 디바이스(802))에 의해 실행되거나 또는 그 장치의 동작을 제어하도록, 유형의 프로그램 운반체(carrier)에 인코딩된 컴퓨터 프로그램 명령의 하나 이상의 모듈로서 구현될 수 있다. 유형의 프로그램 운반체는 전파되는(propagated) 신호 또는 컴퓨터 판독가능 매체일 수 있다. 전파되는 신호는 컴퓨터 판독가능 매체일 수 있다. 컴퓨터 판독가능 매체는 기계 판독가능 저장 디바이스, 기계 판독가능 저장 기판(substrate), 메모리 디바이스, 또는 이들 중 하나 이상의 조합일 수 있다.

"프로세싱 장치"라는 용어는 데이터를 처리하기 위한 모든 장치, 디바이스 및 기계를 포괄하며, 예를 들어, 프로그래머블 프로세서, 컴퓨터, 또는 다중 프로세서 또는 컴퓨터들을 포함한다. 장치는 또한 하드웨어 외에도, 당해 컴퓨터 프로그램에 대한 실행 환경을 생성하는 코드를 포함하고, 코드는 예를 들어, 프로세서 펌웨어, 프로토콜 스택, 데이터베이스 관리 시스템, 운영 시스템, 또는 이들 중 하나 이상의 조합을 구성한다.

컴퓨터 프로그램(프로그램, 소프트웨어, 소프트웨어 애플리케이션, 스크립트 또는 코드로도 알려짐)은 컴파일 또는 인터프리터 언어나 선언적 또는 절차적 언어를 포함하는 모든 형태의 프로그래밍 언어로 작성될 수 있으며, 독립형 프로그램이나 모듈, 컴포넌트, 서브루틴 또는 컴퓨터 환경에서 사용하기에 적합한 그 밖의 유닛을 포함하는 임의의 형태로도 배치될 수 있다. 컴퓨터 프로그램은 파일 시스템의 파일에 반드시 상응해야 하는 것은 아니다. 프로그램은 다른 프로그램 또는 데이터를 보유하는 파일의 일부에 저장되거나(예를 들어, 마크업 언어 문서 내에 저장되는 하나 이상의 스크립트), 당해 프로그램 전용의 단일 파일에 저장되거나, 또는 다수의 조화된(coordinated) 파일들(예를 들어, 하나 이상의 모듈, 서브프로그램, 코드의 부분을 저장하는 파일)에 저장될 수 있다. 컴퓨터 프로그램은 하나의 컴퓨터에서, 또는 한 위치에 배치되거나 또는 다수의 위치에 걸쳐서 분산되고 통신 네트워크에 의해 접속된 다수의 컴퓨터에서 실행되도록 배치될 수 있다.

본 명세서에 설명된 프로세스와 논리 흐름은 하나 이상의 프로그래머블 프로세서에 의해 수행될 수 있고, 이 프로그래머블 프로세서는 입력 데이터에 작용하여 출력을 생성함으로써 기능을 수행하는 하나 이상의 컴퓨터 프로그램들을 실행한다. 예를 들어, FPGA(field programmable gate array) 또는 ASIC(application specific integrated circuit)과 같은 전용 논리 회로가 프로세스와 논리 흐름을 수행하거나, 장치를 구현할 수 있다.

컴퓨터 프로그램의 실행에 적합한 프로세서에는, 예를 들어, 범용 및 전용 마이크로프로세서, 및 임의 종류의 디지털 컴퓨터 중 하나 이상의 프로세서가 있다. 일반적으로, 프로세서는 판독 전용 메모리(ROM), 또는 랜덤 액세스 메모리(RAM), 또는 양자로부터 명령어들과 데이터를 수신한다. 컴퓨터의 필수 구성요소는 명령을 실행하는 프로세서, 및 명령어와 데이터를 저장하는 하나 이상의 메모리 디바이스이다. 컴퓨터의 주요 요소들은 명령어들을 수행하기 위한 프로세서와 명령어들과 데이터를 저장하기 위한 하나 이상의 메모리 디바이스이다. 일반적으로, 컴퓨터는 데이터를 저장하기 위한 하나 이상의 대용량 저장 디바이스(예를 들어, 자기 디스크, 광자기 디스크, 또는 광디스크)를 포함하거나, 또는 이 디바이스와 데이터를 송수신하기 위하여 동작적으로(operatively) 결합될 수 있다. 하지만 컴퓨터는 이러한 디바이스를 반드시 구비할 필요는 없다. 더욱이, 컴퓨터는 예를 들어, 모바일 전화기, 개인 정보 단말(PDA), 모바일 오디오 또는 비디오 재생기, 게임 콘솔, GPS(Global Positioning System) 수신기 등과 같은 다른 디바이스에 내장될 수 있다.

컴퓨터 프로그램 명령어들과 데이터를 저장하기 적합한 컴퓨터 판독가능 매체에는, 예를 들어, 반도체 메모리 디바이스(예를 들어, EPROM, EEPROM, 플래시 메모리 디바이스); 자기 디스크(예를 들어, 내부 하드디스크, 착탈식 디스크); 광자기 디스크; 및 CD ROM과 DVD-ROM 디스크를 포함하는 모든 형태의 비휘발성 메모리, 매체 및 메모리 디바이스가 포함된다. 프로세서와 메모리는 전용 논리 회로에 의해 보완되거나 또는 전용 논리 회로에 통합될 수 있다.

사용자와의 상호작용을 제공하기 위하여, 본 명세서에 설명된 주제의 실시예들은, 정보를 사용자에게 디스플레이하기 위한 디스플레이 디바이스(예를 들어, CRT(cathode ray tube) 또는 LCD(liquid crystal display) 모니터), 키보드 및 포인팅 디바이스(예를 들어, 마우스 또는 트랙볼)를 구비한 컴퓨터에 구현될 수 있다. 사용자는 키보드와 포인팅 디바이스를 이용하여 컴퓨터에 입력을 제공할 수 있다. 사용자와의 상호작용을 제공하기 위하여 다른 종류의 디바이스가 또한 사용될 수 있다. 예를 들어, 사용자에게 제공되는 피드백(feedback)은 예를 들어, 시각 피드백, 청각 피드백 또는 촉각 피드백인 임의 형태의 감각 피드백일 수 있고, 사용자로부터의 입력은 음향, 음성 또는 촉각 입력을 포함하는 임의의 형태로 수신될 수 있다.

본 명세서가 다수의 특정한 구현 세부사항을 포함하고 있지만, 이는 임의 구현예의 범위나 청구할 사항의 범위에 대한 어떠한 제한으로서도 이해되어서는 안 되며, 특정한 구현예들의 특정한 실시예에 고유할 수 있는 특징의 설명으로서 이해되어야 한다. 별개의 실시예의 문맥으로 본 명세서에서 설명된 소정 특징은 조합되어 단일 실시예로 구현될 수도 있다. 반대로, 단일 실시예의 문맥에서 설명한 다양한 특징은 복수의 실시예에서 별개로 구현되거나 어떤 적당한 하위 조합으로서도 구현 가능하다. 또한, 앞에서 특징이 소정 조합에서 동작하는 것으로서 설명되고 그와 같이 청구되었지만, 청구된 조합으로부터의 하나 이상의 특징은 일부 경우에 해당 조합으로부터 삭제될 수 있으며, 청구된 조합은 하위 조합이나 하위 조합의 변형으로 될 수 있다.

마찬가지로, 도면에서 특정한 순서로 동작을 묘사하고 있지만, 그러한 동작이 바람직한 결과를 얻기 위해, 도시한 특정 순서나 순차적인 순서로 수행되어야 한다거나, 설명한 모든 동작이 수행되어야 한다는 것을 의미하는 것은 아니다. 소정 환경에서, 멀티태스킹 및 병렬 프로세싱이 유리할 수 있다. 또한, 상술한 실시예에 있어서 다양한 시스템 구성요소의 분리는 모든 실시예에서 그러한 분리를 요구하는 것으로 이해되어서는 안 되며, 설명한 프로그램 구성요소와 시스템은 일반적으로 단일 소프트웨어 제품으로 통합되거나 또는 복수의 소프트웨어 제품으로 패키지 될 수 있다는 점을 이해되어야 한다.

본 명세서에서 설명한 주제의 특정 실시예가 기술되었다. 그 밖의 실시예는 후술하는 청구범위 내에 속한다. 예를 들어, 청구항에 인용된 동작들은 상이한 순서로 수행될 수 있지만, 여전히 바람직한 결과를 달성한다. 일 실시예로서, 첨부한 도면에 도시한 프로세스는, 바람직한 결과를 얻기 위해, 도시된 특정 순서나 순차적인 순서를 반드시 요구하는 것은 아니다. 소정 구현예에서, 멀티태스킹과 병렬 프로세싱이 효과적일 수 있다.

612: 사전 616: 사전 구축기
614: 병음 테이블 618: 병음 구축기
620: 사전 모델 630: 입력 방법 편집기
632: 사전 트리 634: 병음 트리
636: 병음 분석기 638: 사전 분석기
639: 언어 모델 640: 입력
650: 출력 802: 프로세싱 디바이스
803: 입력 방법 편집기 인스턴스 804, 806: 데이터 저장소
808: 입력 디바이스들 810: 출력 디바이스들
812: 네트워크 인터페이스 816: 네트워크
920: 입력 방법 편집기 시스템 922: IME 엔진

Claims

컴퓨터 구현 방법으로서,
제1 쓰기 체계로 된 제1 문자소(grapheme)를 수신하는 단계;
제2 쓰기 체계로 된 제1 형태소(morpheme)에 대한 제1 쓰기 체계에서의 제1 n-그램 표현(n-gram representation)을 식별하기 위해 제1 쓰기 체계로 된 문자소들의 문자소 그래프를 사용하는 단계―여기서, 제1 n-그램 표현은 제1 문자소를 포함함―;
형태소 그래프에서 하나 이상의 제1 노드를 찾기 위해 상기 제1 n-그램 표현을 사용하는 단계―여기서, 형태소 그래프에서 찾은 제1 노드 각각은 제2 쓰기 체계로 된 하나 이상의 제1 어휘 항목(lexical item)를 표현하고, 하나 이상의 제1 어휘 항목 각각은 상기 제1 n-그램 표현에 의해 표현됨―;
상기 하나 이상의 제1 어휘 항목 각각에 연관된 제1 점수에 기초하여 상기 하나 이상의 제1 어휘 항목으로부터 하나의 제1 어휘 항목을 선택하는 단계; 및
상기 제1 어휘 항목을 사용자 디바이스 상에 디스플레이를 위하여 제공하는 단계를 포함하는 것을 특징으로 하는 컴퓨터 구현 방법.
청구항 1에 있어서,
상기 제1 문자소는 상기 제2 쓰기 체계로 된 음절 일부만을 표현하는 것을 특징으로 하는 컴퓨터 구현 방법.
청구항 1에 있어서,
상기 제1 쓰기 체계로 된 제2 문자소를 수신하는 단계;
상기 제2 쓰기 체계로 된 제2 형태소에 대한 상기 제1 쓰기 체계에서의 제2 n-그램 표현을 식별하기 위해 상기 제1 쓰기 체계로 된 문자소들의 상기 문자소 그래프를 사용하는 단계―여기서, 상기 제2 n-그램 표현은 제2 문자소를 포함함―;
상기 형태소 그래프에서 하나 이상의 제2 노드를 찾기 위해 제2 n-그램 표현을 사용하는 단계―여기서, 상기 형태소 그래프에서 찾은 제2 노드 각각은 상기 제2 쓰기 체계로 된 하나 이상의 제2 어휘 항목을 표현하고, 상기 하나 이상의 제2 어휘 항목 각각은 상기 제2 n-그램 표현에 의해 표현됨―;
제3 어휘 항목와 제4 어휘 항목으로 된 하나 이상의 순열(permutation)을 생성하는 단계―여기서, 상기 제3 어휘 항목은 상기 하나 이상의 제1 어휘 항목으로부터 선택되고, 상기 제4 어휘 항목은 상기 하나 이상의 제2 어휘 항목으로부터 선택됨―;
상기 하나 이상의 순열 각각에 연관된 제2 점수에 기초하여, 상기 하나 이상의 순열로부터 하나의 순열을 선택하는 단계―여기서, 상기 선택된 순열은 상기 제4 어휘 항목이 이어지는 상기 제3 어휘 항목을 포함함―;
상기 선택된 제1 어휘 항목의 상기 제1 점수와 상기 선택된 순열의 상기 제2 점수를 비교하는 단계; 및
상기 비교 결과에 기초하여, 상기 선택된 제1 어휘 항목 또는 상기 선택된 순열을 사용자 디바이스 상에 디스플레이를 위하여 제공하는 단계를 더 포함하는 것을 특징으로 하는 컴퓨터 구현 방법.
청구항 3에 있어서,
상기 제1 문자소는 상기 제2 문자소에 의해 부분적으로만 표현되는 제4 형태소와 다른 제3 형태소의 일부만을 표현하는 것을 특징으로 하는 컴퓨터 구현 방법.
청구항 1에 있어서,
문자소 그래프는 복수의 노드를 포함하고,
노드 각각은 상기 제1 쓰기 체계로 된 문자소를 표현하고,
상기 복수 노드의 진부분집합(proper subset of the plurality of nodes)에 있는 노드 각각은 전체 음절(full syllable)에 상응하고,
상응하는 전체 음절 각각은 문자소 그래프의 상응하는 노드의 문자소들과 상기 상응하는 노드로부터 내려온 상기 노드들의 문자소들을 포함하는 것을 특징으로 하는 컴퓨터 구현 방법.
청구항 5에 있어서,
상기 제1 n-그램 표현은 상기 노드들의 진부분집합에 있는 노드들 중 하나에 상응하는 전체 음절을 표현하는 것을 특징으로 하는 컴퓨터 구현 방법.
청구항 1에 있어서,
상기 형태소 그래프는 복수 노드를 포함하고,
노드 각각은 상기 제2 쓰기 체계로 된 하나 이상의 형태소를 표현하고,
상기 복수 노드의 진부분집합에 있는 노드 각각은 어휘 항목에 상응하고,
상응하는 어휘 항목 각각은 형태소 그래프의 상응하는 노드의 형태소들과 상기 상응하는 노드로부터 내려온 상기 노드들의 형태소를 포함하는 것을 특징으로 하는 컴퓨터 구현 방법.
청구항 7에 있어서,
상기 형태소는 한지 문자(Hanzi character)에 상응하는 것을 특징으로 하는 컴퓨터 구현 방법.
청구항 1에 있어서,
상기 제1 n-그램 표현은 전체 병음 음절의 대표이고,
상기 하나 이상의 어휘 항목(lexical item) 각각은 한지 용어인 것을 특징으로 하는 컴퓨터 구현 방법.
청구항 1에 있어서,
형태소 그래프에서 하나 이상의 노드를 찾기 위하여 제1 n-그램 표현을 사용하는 단계는,
상기 제1 n-그램 표현에 상응하는 문자소 그래프에 있는 제1 노드의 식별자를 선택하는 단계; 및
상기 식별자와 연관된 상기 형태소 그래프에 있는 제2 노드를 찾는 단계를 포함하는 것을 특징으로 하는 컴퓨터 구현 방법.
컴퓨터 구현 방법으로서,
제1 로마자 입력을 수신하는 단계;
병음 입력 그래프에서 제1 병음 음절 노드를 찾기 위해 상기 제1 로마자 입력을 사용하는 단계―상기 병음 입력 그래프는 복수의 병음 음절 노드를 포함하고, 병음 음절 노드 각각은 하나의 로마자에 상응하고, 상기 복수의 병음 음절 노드의 진부분집합에 있는 병음 음절 노드 각각은 하나의 병음 음절에 상응하고, 상응하는 병음 음절 각각은 병음 입력 그래프의 상응하는 병음 음절 노드의 로마자와 상기 상응하는 병음 음절 노드로부터 내려온 상기 병음 음절 노드들의 상기 로마자를 포함함― ;
병음 음절 그래프에서 하나 이상의 제1 한지 문자 노드를 찾기 위해 상기 찾은 병음 음절 노드를 사용하는 단계―상기 병음 음절 그래프는 복수의 한지 문자 노드를 포함하고, 한지 문자 노드 각각은 하나의 병음 음절에 상응하고, 상기 복수의 한지 문자 노드의 진부분집합에 있는 한지 문자 노드 각각은 하나 이상의 제1 한지 용어에 상응하고, 상응하는 하나 이상의 제1 한지 용어 각각은 병음 음절 그래프의 상응하는 한지 문자 노드의 병음 음절들과 상기 상응하는 한지 문자 노드로부터 내려온 상기 한지 문자 노드들의 병음 음절들에 상응하는 한지 문자들을 포함함―; 및
사용자 디바이스에 출력을 위하여, 하나 이상의 제1 한지 용어 각각에 연관된 제1 점수에 기초하여 하나 이상의 한지 문자 노드 중 하나에 상응하는 제1 한지 용어를 선택하는 단계를 포함하는 것을 특징으로 하는 컴퓨터 구현 방법.
청구항 11에 있어서,
제2 로마자 입력을 수신하는 단계;
상기 병음 입력 그래프에서 제2 병음 음절 노드를 찾기 위하여 상기 제2 로마자 입력을 사용하는 단계―여기서, 상기 제2 병음 음절 노드는 상기 제2 로마자 입력을 포함하는 병음 음절을 표현함―;
병음 음절 그래프에서 하나 이상의 제2 한지 문자 노드를 찾기 위하여 찾은 제2 상기 병음 음절 노드를 사용하는 단계―여기서, 찾은 제2 한지 문자 노드 각각은 하나 이상의 제2 한지 용어에 상응함―;
제3 한지 용어와 제4 한지 용어로 된 하나 이상의 순열을 생성하는 단계―여기서, 상기 제3 한지 용어는 상기 하나 이상의 제1 한지 용어로부터 선택되고, 상기 제4 한지 용어는 상기 하나 이상의 제2 한지 용어로부터 선택됨―;
상기 하나 이상의 순열 각각에 연관된 제2 점수에 기초하여, 상기 하나 이상의 순열로부터 하나의 순열을 선택하는 단계―여기서, 상기 선택된 순열은 상기 제4 한지 용어가 이어지는 상기 제3 한지 용어를 포함함―;
상기 선택된 제1 한지 용어의 제1 점수와 상기 선택된 순열의 제2 점수를 비교하는 단계; 및
상기 비교 결과에 기초하여, 상기 선택된 제1 한지 용어 또는 상기 선택된 순열을 상기 사용자 디바이스로의 출력을 위해 제공하는 단계를 더 포함하는 것을 특징으로 하는 컴퓨터 구현 방법.
청구항 11에 있어서,
상기 하나 이상의 한지 문자 노드를 찾기 위해 상기 찾은 병음 음절 노드를 사용하는 단계는
상기 찾은 병음 음절 노드의 식별자를 선택하는 단계; 및
상기 식별자에 연관된 상기 병음 음절 그래프에서 제1 한지 문자 노드를 찾는 단계를 포함하는 것을 특징으로 하는 컴퓨터 구현 방법.
청구항 11에 있어서,
상기 병음 음절 그래프는 패트리샤 트리(patricia trie)인 것을 특징으로 하는 컴퓨터 구현 방법.
시스템으로서,
데이터 처리 장치; 및
데이터 저장소를 포함하고, 상기 데이터 저장소에는
제1 쓰기 체계로 된 문자소들의 문자소 그래프―상기 문자소 그래프는 제1 복수 노드를 포함하고, 상기 제1 복수 노드에 있는 노드 각각은 상기 제1 쓰기 체계로 된 문자소를 나타내고, 상기 제1 복수 노드의 진부분집합에 있는 노드 각각은 전체 음절에 상응하고, 상응하는 전체 음절 각각은 상기 제1 복수 노드에 있는 문자소 그래프의 상응하는 노드의 문자소들과, 상기 제1 복수 노드에 있는 상기 상응하는 노드로부터 내려온 상기 노드들로부터의 문자소들을 포함함―; 및
제2 쓰기 체계로 된 형태소들의 형태소 그래프―상기 형태소 그래프는 제2 복수 노드를 포함하고, 상기 제2 복수 노드에 있는 노드 각각은 제2 쓰기 체계로 된 하나 이상의 형태소를 표현하고, 상기 제2 복수 노드의 진부분집합에 있는 노드 각각은 어휘 항목에 상응하고, 상응하는 어휘 항목 각각은 상기 제2 복수 노드에 있는 형태소 그래프의 상응하는 노드의 형태소들과 제2 복수 노드에 있는 상응하는 노드로부터 내려오는 노드들의 형태소들을 포함함―가 저장되는 것을 특징으로 하는 시스템.
청구항 15에 있어서,
상기 데이터 저장소는 하나 이상의 상기 어휘 항목의 조합을 점수화하는 언어 모델을 더 저장하는 것을 특징으로 하는 시스템.
데이터 처리 장치로 하여금 동작들을 수행가능하게 하는 컴퓨터 프로그램이 수록된 비-일시적인(non-transitory) 컴퓨터 판독가능 매체로서,
상기 동작들은:
제1 쓰기 체계로 된 제1 문자소를 수신하는 동작;
제2 쓰기 체계로 된 제1 형태소에 대한 제1 쓰기 체계에서의 제1 n-그램 표현(n-gram representation)을 식별하기 위해 제1 쓰기 체계로 된 문자소들의 문자소 그래프를 사용하는 동작―여기서, 제1 n-그램 표현은 제1 문자소를 포함함―;
형태소 그래프에서 하나 이상의 제1 노드를 찾기 위해 상기 제1 n-그램 표현을 사용하는 동작―여기서, 형태소 그래프에서 찾은 제1 노드 각각은 제2 쓰기 체계로 된 하나 이상의 제1 어휘 항목을 표현하고, 하나 이상의 제1 어휘 항목 각각은 상기 제1 n-그램 표현에 의해 표현됨―;
상기 하나 이상의 제1 어휘 항목 각각에 연관된 제1 점수에 기초하여 상기 하나 이상의 제1 어휘 항목으로부터 하나의 제1 어휘 항목을 선택하는 동작; 및
상기 제1 어휘 항목을 사용자 디바이스 상에 디스플레이를 위하여 제공하는 동작을 포함하는 것을 특징으로 하는 비-일시적인 컴퓨터 판독가능 매체.
청구항 17에 있어서,
상기 동작들은:
상기 제1 쓰기 체계로 된 제2 문자소를 수신하는 동작;
상기 제2 쓰기 체계로 된 제2 형태소에 대한 상기 제1 쓰기 체계에서의 제2 n-그램 표현을 식별하기 위해 상기 제1 쓰기 체계로 된 문자소들의 상기 문자소 그래프를 사용하는 동작―여기서, 상기 제2 n-그램 표현은 제2 문자소를 포함함―;
상기 형태소 그래프에서 하나 이상의 제2 노드를 찾기 위해 제2 n-그램 표현을 사용하는 동작―여기서, 상기 형태소 그래프에서 찾은 제2 노드 각각은 상기 제2 쓰기 체계로 된 하나 이상의 제2 어휘 항목을 표현하고, 상기 하나 이상의 제2 어휘 항목 각각은 상기 제2 n-그램 표현에 의해 표현됨―;
제3 어휘 항목와 제4 어휘 항목으로 된 하나 이상의 순열(permutation)을 생성하는 동작―여기서, 상기 제3 어휘 항목은 상기 하나 이상의 제1 어휘 항목으로부터 선택되고, 상기 제4 어휘 항목은 상기 하나 이상의 제2 어휘 항목으로부터 선택됨―;
상기 하나 이상의 순열 각각에 연관된 제2 점수에 기초하여, 상기 하나 이상의 순열로부터 하나의 순열을 선택하는 동작―여기서, 상기 선택된 순열은 상기 제4 어휘 항목이 이어지는 상기 제3 어휘 항목을 포함함―;
상기 선택된 제1 어휘 항목의 상기 제1 점수와 상기 선택된 순열의 상기 제2 점수를 비교하는 동작; 및
상기 비교 결과에 기초하여, 상기 선택된 제1 어휘 항목 또는 상기 선택된 순열을 사용자 디바이스 상에 디스플레이를 위하여 제공하는 동작을 더 포함하는 것을 특징으로 하는 비-일시적인 컴퓨터 판독가능 매체.