막힘

Stemming
스키 기술은 스템(스키)을 참조하십시오.등반 기술에 대해서는 등반 용어집 § 스템을 참조하십시오.

언어 형태학 및 정보 검색에서 스템은 굴절된(또는 때로는 파생된) 단어를 어간, 어근 또는 어근 형태(일반적으로 쓰여진)로 줄이는 과정입니다.어간은 어근의 형태학적 어근과 같을 필요는 없다.어간 자체가 유효한 어근이 아니더라도 관련 어근은 보통 같은 어간에 매핑하는 것으로 충분하다.스트로핑 알고리즘은 1960년대부터 컴퓨터 공학에서 연구되어 왔다.많은 검색 엔진은 어간이 같은 단어들을 일종의 쿼리 확장, 즉 결합이라고 불리는 과정으로 동의어로 취급한다.

단어를 줄인 컴퓨터 프로그램 또는 서브루틴은 스템 프로그램, 스템 알고리즘 또는 스템머라고 불립니다.

예

줄 고양이를 수술하는 영어 스템머는 고양이, 고양이, 고양이와 같은 끈을 식별해야 한다.또한 스템 알고리즘을 사용하면 줄기에 대한 fishing, fishing 및 fisher라는 단어를 줄일 수 있습니다.스템은 단어일 필요는 없습니다.예를 들어 포터 알고리즘은 스템 논쟁에 대해 축소, 주장, 주장, 주장 및 아르구스를 제시합니다.

역사

최초의 출판된 스테머는 1968년에 [1]Julie Beth Lovins에 의해 쓰여졌다.이 논문은 초기에 주목할 만한 것이었으며 이 [citation needed]분야의 향후 작업에 큰 영향을 미쳤다.그녀의 논문은 존 W 교수가 알고리즘을 막으려는 이전의 세 가지 주요 시도를 언급하고 있다. 프린스턴 대학의 Tukey는 Michael Lesk가 Gerard Salton 교수의 지도 하에 하버드 대학에서 개발한 알고리즘이며, 캘리포니아 주 로스 알토스의 R&D 컨설턴트의 James L. Dolby가 개발한 세 번째 알고리즘입니다.

나중에 나온 스테머는 마틴 포터에 의해 쓰여졌고 프로그램 저널의 1980년 7월호에 발표되었습니다.이 스테머는 매우 널리 사용되었고 영어 어근에 사용되는 사실상의 표준 알고리즘이 되었다.포터 박사는 스팅과 정보 검색 연구로 2000년에 토니 켄트 스트립스 상을 받았습니다.

Porter streaming 알고리즘의 많은 구현체들이 작성되고 자유롭게 배포되었다. 그러나 이러한 구현체들 중 많은 것들이 미묘한 결함을 가지고 있었다.그 결과, 이러한 스테머들은 그들의 잠재력과 일치하지 않았습니다.이 에러의 원인을 없애기 위해서, Martin Porter는 2000년경에 알고리즘의 정식 무료 소프트웨어(대부분 BSD 라이선스를 취득) 실장을[2] 발표했습니다.그는 Steaming 알고리즘을 작성하기 위한 프레임워크인 Snowball을 구축함으로써 이후 몇 년 동안 이 작업을 확장했고, Steamer와 함께 몇몇 다른 언어들을 위한 개선된 영어 Stemer를 구현했습니다.

Paice-Husk Stemmer는 1980년대 후반 랭커스터 대학의 Chris D Paice에 의해 개발되었으며 반복적인 Stemmer이며 외부에 저장된 일련의 Steining 규칙을 특징으로 합니다.표준 규칙 집합은 '강력한' 스테머를 제공하며 엔딩의 제거 또는 교환을 지정할 수 있습니다.치환 기술을 사용하면 프로세스를 재코딩하거나 부분 일치를 제공하기 위해 별도의 단계가 필요하지 않습니다.또한 Paice는 과도한 스템링 오류와 과소 스템링 오류를 계산하여 스템머를 비교하기 위한 직접 측정법을 개발했습니다.

알고리즘

컴퓨터 과학에서 해결되지 않은 문제:

영어에 완벽한 스템 알고리즘이 있나요?

(컴퓨터 사이언스의 미해결 문제 증가)

성능 및 정확도 및 특정 장애물을 극복하는 방법에 따라 다른 여러 유형의 방지 알고리즘이 있습니다.

단순 스테머는 룩업 테이블에서 굴절된 형태를 검색합니다.이 접근법의 장점은 단순하고 빠르고 쉽게 예외를 처리할 수 있다는 것입니다.단점은 모든 굴절 형태를 표에 명시적으로 나열해야 한다는 것이다. 새로운 단어나 익숙하지 않은 단어는 완전히 규칙적인 단어(예: cats ~ cat)일지라도 취급되지 않으며 테이블이 클 수 있다.영어와 같이 단순한 형태론을 가진 언어의 경우 표의 크기는 보통이지만 터키어와 같이 굴절률이 높은 언어는 각 어근에 대해 수백 개의 잠재적 굴절 형태를 가질 수 있습니다.

검색 접근법에서는 과도한 시스템 [3]구성을 방지하기 위해 예비 음성 부분 태그를 사용할 수 있습니다.

제작 기술

스템머가 사용하는 룩업 테이블은 일반적으로 반자동으로 생성됩니다.예를 들어, 단어가 "실행"인 경우 반전 알고리즘은 자동으로 "실행", "실행", "실행", "실행" 및 "실행" 형식을 생성할 수 있습니다.마지막 두 형식은 유효한 구성이지만 가능성이 [citation needed]낮습니다.

서픽스 스트라이핑 알고리즘

접미사 제거 알고리즘은 굴절 형식 및 루트 형식 관계로 구성된 조회 테이블에 의존하지 않습니다.대신, 입력 단어 형식이 주어진 알고리즘이 루트 형식을 찾기 위한 경로를 제공하는 일반적으로 더 작은 "규칙" 목록이 저장됩니다.규칙의 예는 다음과 같습니다.

  • 단어가 'ed'로 끝나면 'ed'를 제거합니다.
  • 단어가 'ing'으로 끝나는 경우 'ing'을 제거합니다.
  • 단어가 'ly'로 끝나는 경우 'ly'를 제거합니다.

서픽스 스트리핑 접근법은 유지자가 언어학 및 형태학 및 부호화 서픽스 스트리핑 규칙에 대한 충분한 지식을 가지고 있다고 가정할 때 무차별 포스 알고리즘보다 유지보수가 훨씬 간단하다는 이점을 누린다.접미사 제거 알고리즘은 예외적인 관계(예: '란' 및 '실행')를 처리할 때 성능이 낮기 때문에 종종 조잡한 것으로 간주됩니다.접미사 제거 알고리즘에 의해 생성되는 해는 거의 예외 없이 잘 알려진 접미사를 가진 어휘 범주로 제한된다.그러나 이것은 문제가 된다. 왜냐하면 모든 연설이 그렇게 잘 짜여진 규칙들을 가지고 있는 것은 아니기 때문이다.Lemmatization은 이 과제를 개선하기 위해 시도합니다.

프리픽스 스트리핑도 실장할 수 있습니다.물론 모든 언어가 접두사나 접미사를 사용하는 것은 아닙니다.

기타 알고리즘 기준

서픽스 제거 알고리즘은 다양한 이유로 인해 결과가 다를 수 있습니다.이러한 이유 중 하나는 알고리즘이 출력 워드가 특정 언어의 실제 워드여야 하는지 여부를 제한하는지 여부입니다.일부 접근법에서는 해당 단어가 언어 사전(언어 내 모든 단어의 집합)에 실제로 존재할 필요가 없습니다.또는 일부 접미사 스트리핑 접근법은 실제 단어로 존재하는 알려진 모든 형태학적 단어 루트의 데이터베이스(대규모 목록)를 유지한다.이러한 접근법은 결정을 내리기 전에 용어의 존재 여부를 목록에서 확인합니다.일반적으로 용어가 존재하지 않는 경우 대체 액션이 수행됩니다.이 대체 조치에는 몇 가지 다른 기준이 포함될 수 있습니다.출력 용어가 존재하지 않으면 알고리즘이 대체 서픽스 스트리핑 규칙을 시행하는 원인이 될 수 있습니다.

같은 입력 용어에 2개 이상의 서픽스 스트리핑 규칙이 적용되는 경우가 있습니다.이것에 의해, 어느 룰을 적용할지가 불명확해집니다.알고리즘은 (사람의 손으로 또는 확률적으로) 어떤 규칙에 우선순위를 할당할 수 있다.또는 알고리즘은 하나의 규칙 어플리케이션을 거부할 수 있습니다.이는 존재하지 않는 용어가 발생하고 다른 중복되는 규칙은 거부되지 않기 때문입니다.예를 들어 영어 용어의 friendly를 지정하면 알고리즘은 ies 접미사를 식별하고 적절한 규칙을 적용하여 friendl의 결과를 얻을 수 있습니다.Friendl은 사전에서 찾을 수 없기 때문에 규칙이 거부됩니다.

기본적인 서픽스 스트리핑의 개선점 중 하나는 서픽스 치환을 사용하는 것입니다.스트리핑 규칙과 마찬가지로 치환 규칙은 접미사를 대체 접미사로 대체합니다.예를 들어 ies를 y로 대체하는 규칙이 존재할 수 있습니다.이것이 알고리즘에 미치는 영향은 알고리즘 설계에 따라 달라집니다.예를 들어 알고리즘은 서픽스 스트리핑 규칙과 서픽스 대체 규칙이 모두 적용되는 것을 식별할 수 있습니다.제거 규칙은 어휘에 존재하지 않지만 대체 규칙은 존재하지 않으므로 대신 대체 규칙이 적용됩니다.이 예에서는 friendl' 대신 friendly가 됩니다.

더 자세히 살펴보면, 일반적인 기술은 규칙들을 주기적인 방식으로 적용하는 것이다(컴퓨터 과학자들이 말하는 것처럼 반복적으로).이 예제 시나리오에서 서픽스 대체 규칙을 적용한 후 두 번째 패스가 생성되어 용어의 일치 규칙을 식별합니다.여기서 Ly Stripping 규칙이 식별되어 받아들여질 가능성이 있습니다.요약하자면, 우정은 (대체로) 우호적이 되고, 우정은 (벗겨서) 친구가 된다.

이 예에서는 규칙 기반 접근법과 무차별 포스 접근법의 차이도 설명합니다.무차별적인 힘 접근법에서는 알고리즘은 수십만 개의 굴절된 단어 형식의 집합에서 우의를 검색하여 이상적으로 대응하는 루트 형식의 친구를 찾습니다.규칙 기반 접근법에서는 위에서 설명한 세 가지 규칙이 동일한 솔루션에 연속적으로 적용됩니다.검색 알고리즘이 솔루션에 직접 액세스할 수 있기 때문에 brute force 접근법이 느릴 수 있습니다.또한 규칙 기반에서는 몇 가지 옵션과 이들 옵션을 조합하여 최적의 결과를 선택해야 합니다.

Lemmatization 알고리즘

단어의 어간을 결정하는 문제에 대한 보다 복잡한 접근법은 lematization이다.이 과정은 먼저 단어의 일부분을 결정하고 각 부분의 다른 정규화 규칙을 적용하는 것을 포함한다.일부 언어에서는 어근 규칙이 단어의 부분에 따라 달라지기 때문에 어근을 찾기 전에 언어 부분이 먼저 감지됩니다.

이 접근법은 정확한 어휘 범주(음성의 일부)를 얻는 것에 크게 좌우된다.특정 카테고리의 정규화 규칙 사이에 중복이 있지만 잘못된 카테고리를 식별하거나 적절한 카테고리를 생성할 수 없는 경우 접미사 스트리핑 알고리즘에 비해 이 접근방식의 추가 이점이 제한됩니다.기본적인 생각은 스템머가 스템되는 단어에 대한 더 많은 정보를 파악할 수 있다면 더 정확한 정규화 규칙을 적용할 수 있다는 것입니다(서픽스 스트리핑 규칙과 달리 스템을 수정할 수도 있습니다).

확률 알고리즘

확률 알고리즘은 단어의 어근을 식별하기 위해 확률을 사용하는 것을 포함한다.확률적 알고리즘은 확률론적 모델을 개발하기 위해 굴절된 관계를 형성하기 위해 루트 형태의 표에서 훈련(학습)된다.이 모델은 일반적으로 복잡한 언어 규칙의 형태로 표현되며, 접미사 스트리핑 또는 Lematization과 성질이 유사하다.스템은 훈련된 모델에 굴절된 형태를 입력하고 모델이 내부 규칙 집합에 따라 루트 형태를 생성하도록 함으로써 수행되며, 이는 가장 적절한 규칙을 적용하는 것과 관련된 결정 또는 단어를 중단하고 동일한 w를 반환할지 여부를 제외하고 접미사 스트리핑 및 레몬테이션과 유사하다.ord 또는 두 개의 다른 규칙을 순차적으로 적용할지 여부는 출력 워드가 정확할 확률이 가장 높다는 이유로 적용된다(즉, 일반적으로 측정되는 방법으로 부정확할 확률이 가장 낮다).

일부 레마타이즈 알고리즘은 확률적이다. 즉, 단어의 여러 부분에 속할 수 있는 단어가 주어지면 가능성이 각 가능한 부분에 할당된다.이것은 문맥이라고 불리는 주변 단어들을 고려할 수 있다.문맥이 없는 문법은 추가 정보를 고려하지 않습니다.어느 경우든, 가능한 각 음성 부분에 확률을 할당한 후, 가장 가능성이 높은 음성 부분을 선택하고, 거기에서 적절한 정규화 규칙을 입력 단어에 적용하여 정규화(근원) 형식을 생성한다.

n그램 분석

일부 스템 기술은 단어의 n그램 컨텍스트를 사용하여 [4]단어의 올바른 스템을 선택합니다.

하이브리드 어프로치

하이브리드 어프로치는 위에서 설명한 두 가지 이상의 어프로치를 동시에 사용합니다.간단한 예로는 먼저 브루트 포스를 사용하여 룩업테이블을 참조하는 서픽스트리 알고리즘이 있습니다그러나 검색 테이블은 특정 언어로 단어 간의 전체 관계 집합을 저장하는 대신 작게 유지되며 "ran => run"과 같은 "예외 항목"을 저장하는 데만 사용됩니다.이 단어가 예외 목록에 없는 경우 접미사 스트리핑 또는 Lematization을 적용하여 결과를 출력합니다.

스테머 부착

언어학에서 접사라는 용어는 접두사 또는 접미사를 가리킵니다.서픽스를 처리하는 것 외에, 몇개의 어프로치가 공통의 프리픽스를 삭제하려고 합니다.예를 들어, 단어를 무기한으로 지정하면 선행하는 "in"이 삭제할 수 있는 접두사임을 식별합니다.앞에서 언급한 것과 동일한 접근법 중 많은 것이 적용되지만, 부착물 스트리핑이라는 이름으로 통합니다.몇몇 유럽 언어에서 유래한 접사에 대한 연구는 여기에서 [5]찾을 수 있다.

매칭 알고리즘

이러한 알고리즘은 스템 데이터베이스(예를 들어 스템 워드를 포함하는 문서 세트)를 사용합니다.위에서 설명한 바와 같이, 이러한 어간은 반드시 유효한 단어일 필요는 없습니다('브라우즈'와 '브라우징'의 '브라우즈'와 같은 일반적인 하위 문자열).단어를 추출하기 위해 알고리즘은 단어 내의 후보 스템의 상대적인 길이(예를 들어 "be", "been" 및 "being"과 같은 단어의 어간인 짧은 프리픽스 "be"를 "beide"의 어간으로 간주하지 않도록 하는 등)를 데이터베이스에서 추출한다..[citation needed].

언어의 과제

이 분야의 초기 학술 연구의 대부분은 영어(Porter Stemmer 알고리즘의 현저한 사용)에 초점을 맞췄지만, 다른 많은 언어들이 [6][7][8][9][10]조사되었다.

히브리어와 아랍어는 여전히 유래하기 어려운 연구 언어로 여겨진다.영어 스테머는 상당히 사소하지만(예를 들어, "dries"는 동사 "dry"의 3인칭 단수 현재형이고, "axes"는 "axe"와 "axes"의 복수형이며, 목표 언어의 형태학, 맞춤법 및 문자 인코딩이 복잡해짐에 따라 설계하기가 어려워진다.예를 들어, 이탈리아어의 스테머는 영어의 스테머보다 복잡하다(동사 굴절의 수가 많기 때문에), 러시아어의 스테머는 더 복잡하다(명사 편차가 크다), 히브리어의 스테머는 더 복잡하다(비격조 형태론, 모음 없는 문자 체계, 접두사 제거의 필요성 때문에).히브리어 어간은 2자, 3자, 4자까지 가능합니다.

다국어 대응

다국어 스템은 검색 쿼리를 해석할 때 단일 언어에만 적용되는 규칙이 아니라 두 개 이상의 언어의 형태학적 규칙을 동시에 적용합니다.다국어 기조를 사용하는 상용 시스템이 존재합니다.[citation needed]

에러 메트릭

스템핑 알고리즘에는 오버스템과 언더스템의 두 가지 오차 측정이 있습니다.과도한 스템화는 두 개의 다른 굴절어가 같은 어근으로 파생되는 오류입니다만, 잘못된 양의 어근으로 파생되어서는 안 됩니다.언더스템밍은 두 개의 다른 굴절어가 같은 어근에 있어야 하지만 잘못된 부정어(false negative)로 분류되지 않는 오류입니다.Steoping 알고리즘은 각 유형의 오류를 최소화하려고 시도하지만, 한 유형을 줄이면 다른 유형이 증가할 수 있습니다.

예를 들어, 널리 사용되는 포터 스테머는 "범용", "대학", "유니버스"를 "대학"으로 줄인다.이것은 과도한 체계화의 한 예이다: 비록 이 세 단어들은 어원적으로 관련이 있지만, 그들의 현대적 의미는 매우 다른 영역에 있기 때문에, 검색 엔진에서 동의어로 취급하면 검색 결과의 관련성을 떨어뜨릴 수 있다.

포터 스테머에서 언더스템밍의 예로는 "superus" → "superu", "super" → "super", "alumna", "superae" → "alumna" 등이 있다.이 영어 단어는 라틴어의 형태학을 유지하며, 따라서 이러한 유사어들은 결합되지 않는다.

적용들

스밍은 비슷한 기본 뜻을 가진 단어들을 함께 묶는 대략적인 방법으로 사용된다.예를 들어, "수선화"를 언급하는 텍스트는 아마도 "수선화"를 언급하는 텍스트와 밀접하게 관련되어 있을 것이다(s는 제외).그러나 어떤 경우, 형태학적으로 동일한 어간이 있는 단어들은 밀접한 관련이 없는 관용적 의미를 가지고 있다. 즉, "마케팅"을 찾는 사용자는 "시장"을 언급하는 대부분의 문서에는 만족하지 못할 것이다.

정보 검색

스테머는 웹 검색 엔진과 같은 쿼리 시스템의 공통 요소입니다.그러나 영어 쿼리 시스템에 대한 string의 효과는 곧 다소 제한적이라는 것을 알게 되었고, 이것은 초기 정보 검색 연구자들이 string을 일반적으로 [11]무관하다고 생각하게 만들었다.대신 스템이 아닌 n그램 검색을 기반으로 하는 대체 접근법을 사용할 수 있다.또한, 스테머들은 [12][13]영어보다 다른 언어에서 더 큰 혜택을 줄 수 있다.

도메인 분석

string은 도메인 [14]분석에서 도메인 어휘를 결정하기 위해 사용됩니다.

상업용 제품에 사용

적어도 1980년대부터 많은 상업 회사들이 스템을 사용해 왔고 여러 [15][16]언어로 알고리즘과 어휘 스템을 생산해 왔다.

Snowball stemer는 다양한 [17][18]결과를 가진 상업용 어휘 stemer와 비교되어 왔습니다.

구글 검색은 2003년에 [19]어원을 도입했다.이전에는 "물고기"를 검색해도 "낚시"가 반환되지 않았을 것입니다.다른 소프트웨어 검색 알고리즘은 단어 스밍의 용법에 따라 다릅니다.단순히 하위 문자열을 검색하는 프로그램은 분명히 "낚시"에서 "물고기"를 찾을 것이지만, "물고기"를 검색할 때 "물고기"라는 단어의 발생을 찾을 수 없습니다.

텍스트 마이닝

텍스트 마이닝 분석을 수행하기 전 텍스트 전처리 작업에서 String을 사용합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Lovins, Julie Beth (1968). "Development of a Stemming Algorithm" (PDF). Mechanical Translation and Computational Linguistics. 11: 22–31.
  2. ^ "Porter Stemming Algorithm".
  3. ^ 야츠코, V.A.; Y-stemer
  4. ^ McNamee, Paul (September 2005). "Exploring New Languages with HAIRCUT at CLEF 2005" (PDF). CEUR Workshop Proceedings. 1171. Retrieved 2017-12-21.
  5. ^ Jongejan, B. 및 Darianis, H.; ACL-2009의 속행, 제47회 컴퓨터언어학협회 연차총회 및 제4회 국제자연회의에서의 사전, 인, 접미사의 형태학적 변화를 동일하게 다루는 Lemmatization 규칙의 자동 훈련 아시아 자연어 처리 연맹, 싱가포르, 2009년 8월 2-7일, 페이지 145-153 [1]
  6. ^ Dolamic, Liljana, Savoy, Jacques, 동유럽 언어용 스팅 어프로치 (CLEF 2007)
  7. ^ Savoy, Jacques; 프랑스어, 포르투갈어, 독일어, 헝가리어를 위한 경량화 접근법, ACM 응용컴퓨팅 심포지엄, SAC 2006, ISBN 1-59593-108-2
  8. ^ 포포비치, 미르코 및 윌렛, 피터(1992);슬로베니아 텍스트 데이터에 대한 자연어 접근을 위한 억제 효과, 미국정보과학회 저널, 제43권, 제5호(6월), 페이지 384-390
  9. ^ 2005년 CLEF에서 헝가리어로 어원을 변경
  10. ^ Viera, A. F. G. & Virgil, J. (2007);Uma dos algoritmos de radicalizassa em lyngua portuguesa, 정보연구, 12(3), 논문 315
  11. ^ Baeza-Yates, Ricardo 및 Ribeiro-Neto, Bertier(1999년); 현대 정보 검색, ACM Press/Addison Wesley
  12. ^ Camps, Jaap; Monz, Christof; de Rijke, Maarten; 및 Sigurbjörnsson, Börkur(2004); 다국어 텍스트 검색에 대한 언어 의존적 접근법, C.; Gonzalo, J.; Brasler.
  13. ^ Airio, Eija(2006);단일 및 이중언어 IR에서의 단어 정규화 및 분해, 정보 검색 9:249–271
  14. ^ 프레이크스, W.; 프리토디아즈, R.; & Fox, C. (1998년)"DARE: 도메인 분석 및 재사용 환경", 소프트웨어 엔지니어링 연보(5), 페이지 125-141
  15. ^ Language Extension Packs 2011년 9월 14일 Wayback Machine, dtSearch에서 아카이브 완료
  16. ^ Sharepoint 제품 및 테크놀로지를 사용한 다국어 솔루션 구축 2008년 1월 17일 Microsoft Technet Wayback Machine에서 아카이브
  17. ^ CLEF 2003: Stephen Tomlinson은 Snowball stemmers와 Humnbird 어휘적 strining(lematization) 시스템을 비교했다.
  18. ^ CLEF 2004: Stephen Tomlinson "Humbird Search Server를 사용한 핀란드어, 포르투갈어, 러시아어 검색"
  19. ^ The Essentials of Google Search, Web Search 도움말 센터, Google Inc.

추가 정보

외부 링크