임의의 문자열이 영어처럼 들리는지 어떻게 확인합니까?
https://stackoverflow.com/questions/92006
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
입력 단어 목록을 기반으로 문자열을 생성하는 알고리즘이 있습니다.영어 단어처럼 들리는 문자열만 어떻게 분리하나요?즉.버리다 RDLO 유지하면서 주님.
편집하다: 명확히 하자면, 사전에 나오는 실제 단어일 필요는 없습니다.그냥 영어처럼 들리면 됩니다.예를 들어 케알 받아 들여질 것입니다.
해결책
거대한 영어 텍스트의 마르코프 체인을 구축할 수 있습니다.
그런 다음 마르코프 체인에 단어를 입력하고 해당 단어가 영어일 확률이 얼마나 높은지 확인할 수 있습니다.
여기를 보아라: http://en.wikipedia.org/wiki/Markov_chain
페이지 하단에서 markov 텍스트 생성기를 볼 수 있습니다.당신이 원하는 것은 정확히 그 반대입니다.
간단히 말해서:마르코프 체인은 각 캐릭터에 대해 다음 캐릭터가 따를 확률을 저장합니다.메모리가 충분하다면 이 아이디어를 2~3자로 확장할 수 있습니다.
다른 팁
베이지안 필터를 사용하는 쉬운 방법(Python 예제 http://sebsauvage.net/python/snyppets/#bayesian)
from reverend.thomas import Bayes
guesser = Bayes()
guesser.train('french','La souris est rentrée dans son trou.')
guesser.train('english','my tailor is rich.')
guesser.train('french','Je ne sais pas si je viendrai demain.')
guesser.train('english','I do not plan to update my website soon.')
>>> print guesser.guess('Jumping out of cliffs it not a good idea.')
[('english', 0.99990000000000001), ('french', 9.9999999999988987e-005)]
>>> print guesser.guess('Demain il fera très probablement chaud.')
[('french', 0.99990000000000001), ('english', 9.9999999999988987e-005)]
후보 문자열을 토큰화하여 이에 접근할 수 있습니다. 바이그램—인접한 문자 쌍—그리고 영어 바이그램 빈도 표와 비교하여 각 바이그램을 확인합니다.
- 단순한:바이그램이 빈도표에서 충분히 낮은 경우(또는 전혀 없는 경우) 문자열을 타당하지 않은 것으로 거부합니다.(문자열에 "QZ" 바이그램이 포함되어 있나요?거부하다!)
- 덜 단순함:예를 들어 각 바이그램의 빈도를 해당 길이의 유효한 영어 문자열의 평균 빈도로 나눈 곱으로 전체 문자열의 전체 타당성을 계산합니다.이렇게 하면 (a) 고주파수 바이그램 중에서 홀수 저주파 바이그램이 있는 문자열을 허용하고 (b) 임계값보다 낮지만 임계값보다 아주 낮지는 않은 여러 개별 바이그램이 있는 문자열을 거부할 수 있습니다. .
둘 중 하나는 임계값의 조정이 필요하며 두 번째 기술은 첫 번째 기술보다 더 그렇습니다.
트라이그램으로 동일한 작업을 수행하는 것이 더 강력할 수 있지만, "유효한" 문자열 집합이 좀 더 엄격해질 수도 있습니다.그것이 승리할지 여부는 귀하의 지원서에 달려 있습니다.
기존 연구 자료를 기반으로 한 바이그램 및 트라이그램 테이블은 무료로 사용하거나 구매할 수 있습니다(무료로 사용할 수 있는 것을 찾지 못했지만 지금까지 대략적인 Google만 검색했습니다). 그러나 어떤 좋은 것에서든 직접 바이그램 또는 트라이그램 테이블을 계산할 수 있습니다. 크기가 큰 영어 텍스트 코퍼스.각 단어를 토큰으로 살펴보고 각 바이그램을 집계하면 됩니다. 지정된 바이그램을 키로 사용하고 증분된 정수 카운터를 값으로 사용하여 이를 해시로 처리할 수 있습니다.
영어 형태와 영어 음성학은 (유명하게!) 아이소메트릭보다 적기 때문에 이 기술은 영어로 "보이지만" 문제가 되는 발음을 제공하는 문자열을 생성할 수 있습니다.이것은 바이그램이 아닌 트라이그램에 대한 또 다른 주장입니다. 주어진 음소를 생성하기 위해 여러 문자를 순서대로 사용하는 소리를 분석하여 생성되는 기묘함은 n-그램이 전체 소리에 걸쳐 있으면 줄어들 것입니다.(예를 들어 "쟁기"나 "쓰나미"를 생각해 보세요.)
Markov 체인을 사용하여 영어로 들리는 단어를 생성하는 것은 매우 쉽습니다.그러나 뒤로 가는 것은 더 어려운 일입니다.결과에 대해 허용 가능한 오차 한계는 얼마입니까?항상 일반적인 문자 쌍, 삼중 문자 등의 목록을 갖고 이를 기반으로 등급을 매길 수 있습니다.
동일한 작업을 수행하려고 하기 때문에 "발음 가능한" 비밀번호 생성기를 조사해야 합니다.
Perl 솔루션은 다음과 같습니다. 암호화::PassGen, 사전을 사용하여 훈련할 수 있습니다(필요한 경우 다양한 언어로 훈련할 수 있음).사전을 탐색하고 1, 2, 3 글자 시퀀스에 대한 통계를 수집한 다음 상대 빈도를 기반으로 새로운 "단어"를 만듭니다.
나는 영어 단어 사전에 대해 soundex 알고리즘을 실행하고 결과를 캐시한 다음 후보 문자열을 soundex하고 캐시와 일치시키고 싶은 유혹을 받습니다.
성능 요구 사항에 따라 soundex 코드에 대한 거리 알고리즘을 계산하고 특정 허용 범위 내에서 문자열을 허용할 수 있습니다.
Soundex는 구현하기가 매우 쉽습니다 - 참조 위키피디아 알고리즘에 대한 설명입니다.
원하는 작업의 구현 예는 다음과 같습니다.
def soundex(name, len=4):
digits = '01230120022455012623010202'
sndx = ''
fc = ''
for c in name.upper():
if c.isalpha():
if not fc: fc = c
d = digits[ord(c)-ord('A')]
if not sndx or (d != sndx[-1]):
sndx += d
sndx = fc + sndx[1:]
sndx = sndx.replace('0','')
return (sndx + (len * '0'))[:len]
real_words = load_english_dictionary()
soundex_cache = [ soundex(word) for word in real_words ]
if soundex(candidate) in soundex_cache:
print "keep"
else:
print "discard"
분명히 read_english_dictionary의 구현을 제공해야 합니다.
편집하다:"KEAL"의 예는 "KEEL"과 동일한 soundex 코드(K400)를 갖기 때문에 괜찮습니다.실패율에 대한 아이디어를 얻으려면 거부된 단어를 기록하고 수동으로 확인해야 할 수도 있습니다.
실제 영어 단어여야 합니까, 아니면 영어 단어처럼 보이는 문자열이어야 합니까?
그들이 단지 닮아야 한다면 가능한 영어 단어를 사용하면 실제 영어 텍스트에 대한 통계 분석을 수행하고 어떤 문자 조합이 자주 나타나는지 알아낼 수 있습니다.그런 다음에는 너무 가능성이 없는 문자열을 버릴 수 있습니다. 물론 그 중 일부는 실제 단어일 수도 있습니다.
또는 사전을 사용하여 사전에 없는 단어를 거부할 수도 있습니다(복수형 및 기타 변형에 대한 일부 허용 포함).
사전(인터넷에서 무료로 제공)과 비교할 수 있지만 CPU 사용량 측면에서 비용이 많이 들 수 있습니다.그 외에는 프로그래밍 방식으로 다른 방법을 알지 못합니다.
상당히 복잡한 작업처럼 들립니다!내 머리 꼭대기에서 자음 음소는 그 앞이나 뒤에 모음이 필요합니다.하지만 음소가 무엇인지 결정하는 것은 꽤 어려울 것입니다!아마도 수동으로 목록을 작성해야 할 것입니다.예를 들어, "TR"은 괜찮지만 "TD"는 그렇지 않습니다.
아마도 영어 단어 데이터베이스에 대해 SOUNDEX 알고리즘을 사용하여 각 단어를 평가할 것입니다.SQL 서버에서 이 작업을 수행하는 경우 대부분의 영어 단어 목록이 포함된 데이터베이스를 설정하는 것이 매우 쉬울 것이며(무료로 사용 가능한 사전 사용) MSSQL 서버에는 사용 가능한 검색 알고리즘으로 SOUNDEX가 구현되어 있습니다.
물론 원하는 경우 어떤 언어로든 직접 구현할 수 있지만 꽤 힘든 작업이 될 수 있습니다.
이렇게 하면 각 단어가 기존 영어 단어와 얼마나 비슷한지 평가할 수 있으며 결과를 허용할 수준에 대한 제한을 설정할 수 있습니다.여러 단어에 대한 결과를 결합하는 방법을 고려하고 테스트를 기반으로 허용 한계를 조정할 수도 있습니다.
파이 테스트와 우연 지수를 살펴 보는 것이 좋습니다. http://www.threaded.com/cryptography2.htm
나는 몇 가지 간단한 규칙을 제안하고 표준 쌍과 세 쌍이 좋을 것입니다.
예를 들어, 영어로 발음되는 단어는 일부 이중모음과 표준 자음 쌍을 제외하고 모음-자음-모음의 패턴을 따르는 경향이 있습니다(예:th, 즉 및 ei, oo, tr).그러한 시스템을 사용하면 영어처럼 들리지 않는 거의 모든 단어를 제거해야 합니다.자세히 살펴보면 영어처럼 들리는 많은 단어를 제거할 수 있지만 더 넓은 범위의 단어를 허용하는 규칙을 추가하고 알고리즘을 수동으로 '훈련'할 수 있다는 것을 알 수 있습니다.
거짓음성(예:나는 리듬이 단어라는 점을 명시적으로 코딩하지 않고 '리듬'을 포함하는 규칙을 생각해 낼 수 없을 것이라고 생각하지만 필터링 방법을 제공할 것입니다.
나는 또한 확실히 영어 의미를 지닌 단어인 문자열보다는 영어 단어(발음할 때 합리적으로 들리는)일 수 있는 문자열을 원한다고 가정합니다.
