현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

text 패턴 매칭 정도 알아내기.

서지훈의 이미지
글쓴이: 서지훈 / 작성시간: 월, 2005/03/28 - 5:35오후

예를 들어 A라는 문서와 B라는 문서가 있으면, 이 둘의 매칭 정도를 알아 낼 수 있는 프로그램이나 라이브러리가 필요합니다.
대도록이면 A와 B의 매칭률이 백분율로 나왔으면 하는 바램이 있습니다.
욕심이 좀 과한거 같기는 한데...
혹시라도 이런 방법 아시면 적극 추천을 좀...
미리미리 감사드리고, 즐 퇴근들 하시길 ~~~

<어떠한 역경에도 굴하지 않는 '하양 지훈'>

Forums: 
프로그래밍 QnA
익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 월, 2005/03/28 - 5:50오후

글쎄요.
문서의 일치성(내용보다는, 외관상이랄까?) diff같은 것을 원하시는지?

아님 텍스트에 나오는 단어를 빈도 카운트 후에 통계적으로 유사도를 구하고 싶으신지? 이 경우 베이지언 메서드같은 현재 스팸메일 검사방법으로 많이 사용되는
툴들에 구현되어 있지요. 통계자료 모으면서, 말로는 인공지능 어쩌구 학습 어쩌구라는 거창한 단어도 쓰기도 한다는...
그외에도 Document Clustering이라는 분야에서 많이들 사용하고, 검색엔진등 만드는 쪽에서도 쓴다는...

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 월, 2005/03/28 - 5:52오후

음 그리고, 대충 검색해주는 agrep를 검색해보세요.

fromdj의 이미지

글쓴이: fromdj / 작성시간: 월, 2005/03/28 - 8:19오후

몇년전쯤에 미국의 한 교수가 학생들이 레포트를 카피해서
내지 않나 하는 의심에 .. 검사 프로그램을 만든적이 있습니다.
특정 단어나열이 n번 이상 일치할 경우의 빈도같은 걸로
했다고 아는데.. 재밌겠네요 만들어 보면

^^ be cool ~
http://fromdj.pe.kr

pynoos의 이미지

글쓴이: pynoos / 작성시간: 월, 2005/03/28 - 11:27오후

http://bbs.kldp.org/viewtopic.php?t=53778

아주 비슷한 문제를 raymundo님께서 질문하셨지요. 혹시나 참고가 되시길.

---
http://coolengineer.com

urmajest의 이미지

글쓴이: urmajest / 작성시간: 화, 2005/03/29 - 12:10오전

사실 어떤 비교를 원하시는지에 따라 좀 다른 문제인데..

예를 들어 diff는 한 줄 단위로는 exact matching을 하고,

전체 문서에 대해서는 LCS(longest common sequence)로

매칭을 합니다.

LCS가 적절한 점은 인위적인 조작을 찾아내기에 용이한 것 같네요.

직접 구현하셔도 좋겠고, 굳이 존재하는 tool을 이용하신다면,

텍스트의 모든 문자뒤에 '\n'을 삽입하셔서 diff한 후 결과의 행수를

세어보면 되겠네요 ^^

또 다른 예로는 어떤 텍스트(T)와 패턴(P)이 있을 때,

P가 T의 어느 부분에서(즉, 모든 부분에서) 몇 %의 일치도를 보이는지 계산할 수 있는

알고리즘이 있습니다. O(a n log(k)) time이구, a는 알파벳 갯수, n은 T의 길이, k는 P의 길이 입니다.

convolution을 이용하는 알고리즘인데 O(nlog(n))을 달성하기 위해선

할 수 없이 DFT와 inverse DFT를 해야하기 때문에 복잡한 점도 있지만,

현재로선 state of the art라고 하네요 ^^

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.