[완료]정규표현식은 구체적일수록 빠른가요, 간결할수록 빠른가요?
글쓴이: klara / 작성시간: 금, 2008/03/28 - 7:27오후
정규표현식을 이용해서 XML문서의 특정 엘리먼트의 특정 속성을 찾을려고 하는데요.
예를 들어서 이런 걸 매칭시킬려고 할려고 합니다.
보통은 이렇게 하면 될꺼같은데요, 만약에 number라는 속성은 Word에만 있는 속성이라고 하면
<.*\s+number\s*="(\d+)"\s*>
이렇게 매칭시켜도 결과같습니다.(여기서 \s는 공백문자, \d는 숫자입니다.)
이런 경우 처음꺼처럼 구체적으로 Word안의 number를 찾는거랑, 두번째처럼 간단하게 number를 찾는거중에 어느쪽이 더 빠를까요?
혹시 구현 방법에 따라 다르다면 정답은 없는거겠지만, 일반적인 정규표현식의 효율문제가 있다면 알려주시면 감사하겠습니다.
참고로 전 Qt의 QRegExp 클래스를 이용해서 정규표현식을 이용하고 있습니다.
그리고 제가 이제막 정규표현식 쓰기 시작한지라 저 정규표현식 자체가 잘하시는 분에게는 허접해보일지라도 이해해주시기 바랍니다.
Forums:
DFA로 변환 안하고
DFA로 변환 안하고 어떻게 달리 처리한다면 몰라도,
일반적으로는 정규식으로부터 minimized DFA를 구성해서 처리하며,
동일한 언어를 표현하는 minimized DFA는 유일합니다.
따라서 정규식을 아무렇게나 쓰더라도 성능은 언제나 똑같으니
본인이 알아보기 편하게만 쓰면서 틀리지 않으면 장땡입니다.
다만 위와 같은 경우는 실제로 다른 언어를 나타내는 DFA인데
지금 입력으로 들어오는 문자열이 제한되어 있기 때문에 같게 되는 것이니까 좀 다른 문제겠군요.
구현에 따라 다를텐데, 정규식 처리가 상식적인 수준에서 효율적이라면 <Word 를 먼저 매칭하는 것이 일반적으로 빠를 겁니다. 왜냐하면 정규식이란 것이 실패할 때까지 계속 탐색해 나가므로 쓸데없이 DFA를 계속 돌리고 있을 필요 없이, 첫 5자가 <Word 가 아니라면 바로 다음 글자로 시작점을 옮길 수 있습니다.
@ 사실 제가 생각하기에 현실적으로 더 중요한 문제는 XML 문법을 분석하는 라이브러리를 쓰면 그냥 딱 떨어지는 문제인데 왜 XML 문법분석기를 이용하지 않는지, 또 정규식을 써야 할 이유가 있다 하더라도 효율에 있어서 이 부분이 특별한 병목이라 number 탐색하는 정규식 효율에 신경을 쓸 가치가 있는지 이것부터 생각해 보아야 하지 않을까 합니다.
[예진아씨 피카사 웹앨범] 임예진 팬클럽 ♡예진아씨♡ http://cafe.daum.net/imyejin
답변감사합니다.사
답변감사합니다.
사실 XML이 아니라 제대로 태그가 열리고 닫히거나 하지 않는 HTML문서 같은 SAMI자막 파일을 파싱하고 있습니다.
예를 들어
<Sync Start=100><P Class="KRCC">어쩌구
<Sync Start=200><P Class="KRCC">저쩌구
이런식으로 SAMI자막파일은 사실상 짝맞춰서 태그 열고 닫게끔 만들어진 파일이 하나도 없더라구요.
그래서 Qt자체의 XML파싱 클래스들로 파싱할수 있을까 시도해봤는데 이경우 제대로된 XML문서가 아니라 파싱이 제대로 안되기에 직접 파싱을 하고 있습니다.
만약에 한영통합자막에 한언어당 천개쯤의 자막이 들어있다면 각각 언어별로 Start가 천번, Class가 천번 매칭되야하는 셈이니까 도합 4천번이길래 이정도면 조금이라도 빠른쪽을 쓰는데 좋지 않을까 해서 질문드렸습니다.(Word=Sync이고, number=Start인 셈입니다)
인용:(여기서 \s는
질문에 답변 달 분들 중에 이 걸 모르시는 분은 없을 것 같습니다.
이럴 경우 먼저 속도부터 측정해 보기를 권합니다. 그리고 이경우는간단하게라고 말한 것처럼 너무 간단해서 위의 답변한 분 말대로 상식적으로 생각하면 될 것 같습니다.
QT는 NFA의 일종을 쓰고 있습니다. 그리고 POSIX를 따르는 것 같습니다(제가 확인한 봐로는). 이말은 가능한 제일 길게 맞는 것을 찾는다는 얘깁니다. 이런 상황에서는 효율적인 정규식 표현을 사용하는 것이 중요합니다.
답변감사합니다. \s,\d
답변감사합니다.
\s,\d에 대한 설명은, 제가 정규표현식에 대해 찾아보다보니 이런 키워드들은 정규표현식을 지원하는 곳마다 조금씩 다른듯 하여서 혹시나 Qt에서만 쓰는 건 아닐까 싶어 달아놓은 것이었는데 쓸데없는 걱정이었나보네요. 죄송합니다.
Qt의 정규표현식에는 setMinimal이란 함수가 있어서, 길게 매칭시킬지 짧게 매칭시킬지를 결정할 수 있는데, 이게 혹시 NFA와 DFA를 바꿔주는 건지는 잘 모르겠습니다.
아무튼 조언해주신대로 직접 시간을 재봤더니, 자막이 3천개쯤되는 파일을 파싱할 경우 0.1초 정도차이로 imyejin님의 말씀대로 구체적으로 지정하는 경우가 더 빠르게 나오네요.
진작에 속도를 재봤으면 질문할 필요도 없었을 텐데, 그 생각을 미처 못했습니다.
댓글 달기