문자열 메트릭

수학 및 컴퓨터 과학에서 문자열 메트릭(끈 유사성 메트릭 또는 문자열 거리 함수로도 알려져 있음)은 대략적인 문자열 일치 또는 비교와 퍼지 문자열 검색에서 두 텍스트 문자열 사이의 거리("역 유사성")를 측정하는 메트릭이다. 문자열 메트릭(예: 문자열 매칭 대비)의 요구사항은 삼각형 불평등 충족이다. 예를 들어, 현악 「샘」과 「사뮤엘」은 가까운 것으로 생각할 수 있다.^[1] 문자열 메트릭은 알고리즘별 거리 표시를 나타내는 숫자를 제공한다.

가장 널리 알려진 끈 측정법은 레벤슈테인 거리(편집 거리라고도 한다)^[2]라고 불리는 초보적인 것이다. 두 입력 문자열 사이에서 작동하며, 한 입력 문자열을 다른 입력 문자열로 변환하는 데 필요한 대체 및 삭제 횟수에 해당하는 숫자를 반환한다. 레벤슈테인 거리와 같은 단순한 문자열 지표가 음성, 토큰, 문법 및 문자 기반 통계 비교 방법을 포함하도록 확장되었다.

스트링 메트릭스는 정보 통합에 많이 사용되며, 현재 사기 탐지, 지문 분석, 표절 탐지, 온톨로지 병합, DNA 분석, RNA 분석, 이미지 분석, 증거 기반 기계 학습, 데이터베이스 데이터 중복 제거, 데이터 마이닝, 증분 검색, 데이터 통합, 멀웨어 디텍 등의 영역에서 사용되고 있다.tion, 그리고 의미론적 지식 통합.

문자열 메트릭 목록

선택한 문자열 측정 예제

이름	예.
해밍 거리	"카롤린"과 "kathrin"은 3이다.
레벤슈테인 거리 및 다메라우-레벤슈테인 거리	고양이와 앉아있는 거리는 3이다. 키튼 → 시튼 ("k"에 대한 "s"의 표시) 시튼 → 시틴 (e에 대한 "i"의 표시) sittin → sittin (끝에 "g"의 표시).
자로-윙클러 거리	자로윙클러디스트("MARTHA","MARHTA") = $d_{j}={\frac {1}{3}}\left({\frac {m}{ s_{1} }}+{\frac {m}{ s_{2} }}+{\frac {m-t}{m}}\right)={\frac {1}{3}}\left({\frac {6}{6}}+{\frac {6}{6}}+{\frac {6-{\frac {2}{2}}}{6}}\right)=0.944$ $m$ $m$ 은 $m$ (는) 일치하는 문자 수입니다. $t$ $t$ 은 $t$ (는) 전이 수의 절반이다.`"MARTHA"[3]!=H, "MARHTA"[3]!=T`).
가장 빈번한 k 문자	MostFreqKeySimilarity('리서치', '추적', 2) = 2

참조

^ Lu, Jiaheng; et al. (2013). "String similarity measures and joins with synonyms". Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data: 373–384. doi:10.1145/2463676.2465313. ISBN 9781450320375.
^ Navarro, Gonzalo (2001). "A guided tour to approximate string matching". ACM Computing Surveys. 33 (1): 31–88. doi:10.1145/375360.375365. hdl:10533/172862.
^ Shlomi Dolev; Mohammad, Ghanayim; Alexander, Binun; Sergey, Frenkel; Yeali, S. Sun (2017). "Relationship of Jaccard and edit distance in malware clustering and online identification". 16th IEEE International Symposium on Network Computing and Applications: 369–373.
^ Cohen, William; Ravikumar, Pradeep; Fienberg, Stephen (2003-08-01). "A Comparison of String Distance Metrics for Name-Matching Tasks": 73–78. {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)

외부 링크

https://web.archive.org/web/20070304092115/http:///www.dcs.shef.ac.uk/~sam/stringmetrics.www.dcs.shef.ac.uk/#qgram 상당히 완전한 개요 웨이백 머신의 Archive index
카네기 멜론 대학교 오픈소스 도서관
StringMetric 프로젝트 String 메트릭스 및 음성 알고리즘의 Scala 라이브러리
일반적인 문자열 메트릭 구현을 포함하는 JavaScript 자연 언어 처리 라이브러리 자연 프로젝트

[1] Lu, Jiaheng; et al. (2013). "String similarity measures and joins with synonyms". Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data: 373–384. doi:10.1145/2463676.2465313. ISBN 9781450320375.

[2] Navarro, Gonzalo (2001). "A guided tour to approximate string matching". ACM Computing Surveys. 33 (1): 31–88. doi:10.1145/375360.375365. hdl:10533/172862.

[3] Shlomi Dolev; Mohammad, Ghanayim; Alexander, Binun; Sergey, Frenkel; Yeali, S. Sun (2017). "Relationship of Jaccard and edit distance in malware clustering and online identification". 16th IEEE International Symposium on Network Computing and Applications: 369–373.

[4] Cohen, William; Ravikumar, Pradeep; Fienberg, Stephen (2003-08-01). "A Comparison of String Distance Metrics for Name-Matching Tasks": 73–78. {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)

[1]

[2]

[4]

v t 줄들
문자열 메트릭	대략적인 문자열 일치 비트맵 알고리즘 다메라우-레벤슈테인 거리 거리 편집 게슈탈트 패턴 매칭 해밍 거리 자로-윙클러 거리 리 거리 레벤슈테인 오토매틱 레벤슈테인 거리 바그너-피셔 알고리즘
문자열 검색 알고리즘	아포토리코-지안카를로 알고리즘 보이어-무어 문자열 검색 알고리즘 보이어-무어-호스풀 알고리즘 크누스-모리스-프라트 알고리즘 라빈-카프 알고리즘
다중 문자열 검색	아호코라식 코멘트-발터 알고리즘
정규식	정규 표현 엔진의 비교 정규문법 톰프슨의 건설 비결정론적 유한자동화
시퀀스 정렬	허슈베르크 알고리즘 니들먼-운슈 알고리즘 스미스-워터맨 알고리즘
데이터 구조	DAFSA 접미사 배열 자동 접미사 접미사 트리 일반화 접미사 트리 밧줄 3차 검색 트리 트라이
기타	파싱 패턴 매칭 압축 패턴 매칭 가장 긴 공통 부분 가장 긴 공통 하위 문자열 순차 패턴 마이닝 정렬

Search

문자열 메트릭

네임스페이스

더

목차

문자열 메트릭 목록

선택한 문자열 측정 예제

참조

외부 링크