현재 위치

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

[질문]비슷한 문자 찾기

oprsystem의 이미지
글쓴이: oprsystem / 작성시간: 수, 2005/01/05 - 5:58오후

안녕하세요..

비슷한 문자를 찾아내는 알고리즘을 생각하는 중입니다.

예를 들어서 ABCD 와 비슷한 문자인
A BCD
AECD
XBCD
이런식으로 매칭이 되는것을 찾아냈으면 하는데.. 마땅히
아이디어가 떠오르지 않습니다.

답변 부탁 드립니다..

Forums: 
프로그래밍 QnA
doldori의 이미지

글쓴이: doldori / 작성시간: 수, 2005/01/05 - 6:07오후

터보C정복에 나오는 숫자 맞추기 게임 비슷하게 하면 되지 않을까요?
그러니까 글자와 자리가 모두 일치하면 몇 점, 글자만 일치하고 자리가 다르면
몇 점... 자릿수가 얼마나 다르냐에 따라 가중치를 둘 수도 있겠죠. 그래서 총점 얼마
이상이면 비슷하다고 판정하는 식이요. 사람이 느끼는 것과 비슷한 결과가 나오려면
점수를 튜닝하는 과정이 필요하겠네요.

버려진의 이미지

글쓴이: 버려진 / 작성시간: 수, 2005/01/05 - 6:19오후

저는 비트맵 같은걸 사용하면 되겠다고 생각했어요.

문자를 이루는 비트맵은 RGB 255,255,255와 0,0,0으로만 이루어져 있고, 이것들의 모든 픽셀을 AND연산하는 겁니다. 그래서 0,0,0이 몇개 이상이면 비슷한 글자라던지 이런 룰을... (노가다가 필요하다는 단점이 OTL)

버려진의 이미지

글쓴이: 버려진 / 작성시간: 수, 2005/01/05 - 6:20오후

아니면 미리 비슷한 문자들의 목록을 갖고 있어도 되겠는데요? ^^;

(용도가 무엇인지..)

oprsystem의 이미지

글쓴이: oprsystem / 작성시간: 수, 2005/01/05 - 6:35오후

용도는 목록을 자동화 시키기 위해서 입니다.

목록이 150개쯤 되는데 이전 목록과 비교하는 작업을 사람이 하다 보니
실수도 많고 시간도 걸리고 해서 입니다.

목록이 같은 항상 같은 문자열을 가지고 있다면 비교하기가 쉬운데
목록을 작성하는 사람에 따라서 약간씩 틀리게 써서 이러한 방법을
고안중입니다.

황혼보다 어두운 자여
내 몸에 흐르는 피보다 더 붉은 자여
시간의 흐름 속에 파뭍힌 위대한 그대의 이름을 걸고 나 여기서 어둠에 맹세하노라
우리 앞을 가로막고 있는 모든 어리석은 자 들에게
나와 그대의 힘을
위대한 파멸의 힘을 보여줄 것을

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 수, 2005/01/05 - 7:00오후

agrep인지 유사한 프로그램이 있는 것으로 알고 있습니다.

Prentice의 이미지

글쓴이: Prentice / 작성시간: 수, 2005/01/05 - 7:01오후

http://www.tgries.de/agrep/

리눅스용 패키지/Makefile등을 찾으신다면

http://packages.debian.org/unstable/text/agrep

sozu의 이미지

글쓴이: sozu / 작성시간: 수, 2005/01/05 - 7:14오후

Longest Common Subsequence 를 이용해서 결과값이 몇 이상이면 비슷한 문자열이다 라고 정의해서 사용해도 되지 않을까요?

예를 들어서 ABCD 와 LCS 를 돌렸을때
A BCD -> 4
AECD -> 3
XBCD -> 3

의 결과값이 나오겠죠.

-----------
청하가 제안하는 소프트웨어 엔지니어로써 재미있게 사는 법
http://sozu.tistory.com

정지용의 이미지

글쓴이: 정지용 / 작성시간: 수, 2005/01/05 - 8:49오후

Edit distance란 개념이 있습니다.

string A와 B를 비교할 때, A에서 몇번의 insertion / deletion / substitution 단계를 거쳐 B로 갈 수 있는 지를 비교하는...

구글님께 여쭤보면 자세한 알고리즘이...

;)

서지훈의 이미지

글쓴이: 서지훈 / 작성시간: 수, 2005/01/05 - 9:59오후

일단 매칭의 기준이 뭔지 부터 정하셔야 할듯...
그렇지 않고선 결론을 얻기가 힘드네요.

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

#include <com.h> <C2H5OH.h> <woman.h>
do { if (com) hacking(); if (money) drinking(); if (women) loving(); } while (1);

nohmad의 이미지

글쓴이: nohmad / 작성시간: 수, 2005/01/05 - 10:24오후

PHP의 빌트인 함수에 들어있는 것중에 similar_text와 levenshtein이 있는데 요것도 참고가 될지 모르겠네요.

http://kr.php.net/similar_text
http://kr.php.net/levenshtein

----
http://nohmad.tumblr.com/

oprsystem의 이미지

글쓴이: oprsystem / 작성시간: 목, 2005/01/06 - 9:04오전

답변 감사합니다..
도움이 많이 되었습니다. :)

황혼보다 어두운 자여
내 몸에 흐르는 피보다 더 붉은 자여
시간의 흐름 속에 파뭍힌 위대한 그대의 이름을 걸고 나 여기서 어둠에 맹세하노라
우리 앞을 가로막고 있는 모든 어리석은 자 들에게
나와 그대의 힘을
위대한 파멸의 힘을 보여줄 것을

cinsk의 이미지

글쓴이: cinsk / 작성시간: 목, 2005/01/06 - 9:22오전

dict와 dictd 소스를 보면 될 것 같습니다.

C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
Korean Ver: http://cinsk.github.io/cfaqs/

kkb110의 이미지

글쓴이: kkb110 / 작성시간: 월, 2005/01/10 - 1:02오전

지문 인식이라던지 화상 인식, 필기체 인식은 신경망을 씁니다.

텍스트검색에 신경망 쓰는걸 연구해보면 재밌을거같군요

아직 그런신경망은 못봤습니다만;

mach의 이미지

글쓴이: mach / 작성시간: 월, 2005/01/10 - 10:36오전

Lucene이란 검색엔진을 보면, 원하시는 검색도 포함되어 있는듯합니다.
시간이 넉넉하시다면, 이를 검토해보심이 어떨지?

아래 참고는 query의 예를 담고 있습니다.
* 참고 : http://jakarta.apache.org/lucene/docs/queryparsersyntax.html
* 100% Java로 구현되어 있음; 검색해보면 C++ 이나, C#구현도 어렵지 않게 찾을 수 있을듯.

------------------ P.S. --------------
지식은 오픈해서 검증받아야 산지식이된다고 동네 아저씨가 그러더라.

blitzerg의 이미지

글쓴이: blitzerg / 작성시간: 목, 2005/01/13 - 9:31오후

신경망 쓰세요. 텍스트 인식은 아주 초보적인 수준이니 어렵지 않게 만들 수 있을겁니다.

댓글 달기

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

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.