莫爾斯沒有分隔符 - 最好的算法

在摩爾斯電碼中有個點和破折號在一組1-4中用分隔符隔開。每個組意味着一個字母。詞語之間有兩個分隔符。三句之間。莫爾斯沒有分隔符 - 最好的算法

解密基本莫爾斯電碼的申請很容易實現。但我的問題是，如何解決這個問題，什麼時候沒有分隔符？我知道會有大量無稽之談的結果，但那不是我的觀點。我只需要以最有效的方式獲得所有可能的結果。

這將是一個輸入：

......-...-..---

，這將是衆多成果之一：

hello

你會怎麼做呢？

來源

2016-01-25 Martin Heralecký

請注意，數字都是五個點/破折號。 –

是否有一些原始文本比其他人更可能？（例如，你知道原始文本大部分是英文文本嗎？）如果你知道字符概率（或甚至更好，字符對或三元組的概率等），那麼使用隱馬爾可夫模型將給出*多*更多信息輸出。你可以例如確定最可能的整體解碼。 –

讀完dit或dah後，您有兩種選擇：終止該字母或繼續當前字母。這會導致代碼中出現很多分叉現象，並且遞歸方法可能是實現此目的的好方法。

保留目前爲止可能的字符串的緩衝區，並在打印結束時打印（或存儲）結果，並且它與字母的結尾一致。

下面是用C實現：

#include <stdlib.h> 
#include <stdio.h> 
#include <string.h> 

static const char *letter = "**ETIANMSURWDKGOHVF*L*PJBXCYZQ**"; 

void morse_r(char *buf, int len, const char *str, int code) 
{ 
    if (*str == '\0') { 
     // end of string; print if staring new letter 
     if (code == 1) printf("%.*s\n", len, buf); 
    } else if (code < 16) { 
     if (*str == '.') code = 2 * code;      
     if (*str == '-') code = 2 * code + 1; 

     // continue letter 
     morse_r(buf, len, str + 1, code); 

     // start new letter 
     buf[len++] = letter[code]; 
     morse_r(buf, len, str + 1, 1); 
    } 
} 

void morse(const char *str) 
{ 
    char buf[strlen(str)]; 

    morse_r(buf, 0, str, 1); 
} 

int main() 
{ 
    morse("......-...-..---"); 

    return 0; 
}

這個實現是非常簡單的。它使用簡單的查找機制，並不檢查信件是否真實存在。（letter數組中的星號是有效的莫爾斯電碼，但它們不是拉丁字母。）

這種方法也是相當暴力：它重新計算反覆的尾部。記憶尾巴將爲處理器爲孤獨的字符串節省大量額外的工作。

而且，正如你所知道的，會有一些無意義的結果。上面的代碼產生20569個字符串（其中一些帶有星號，即無效）。當你在路上進行合理性或字典檢查時，可以防止許多遞歸。例如，連續的許多點會產生許多重複的Es的無意義詞彙。

編輯：正如Jim Mischel指出的那樣，摩爾斯電碼查找工作原理的解釋是按順序進行的。 Yves Daoust在他的回答中提到了一個提示。 A trie是用於存儲單詞的樹形結構;每個節點可以有像字母表中的字母一樣多的孩子。莫爾斯電碼只有兩個字母：dit（.）和dah（-）。莫爾斯碼樹是一個二叉樹。

嘗試通常是稀疏的;單詞相當長，許多字母組合不存在。莫爾斯嘗試很密集：莫爾斯字母編碼很短，幾乎每一個cobmination被使用。樹可以存儲爲線性「平坦」陣列，類似於heap。數組中的節點由索引i表示。左邊的孩子然後是2*i和右邊的孩子2*i + 1。

更好和更詳細的解釋可以在answer I posted找到另一個莫爾斯相關的問題，我從上面的例子中採用了查找代碼。

來源

2016-01-25 06:55:09

一個有趣的算法。除了你應該解釋你的'letter'數組是一個二進制樹，並且你的算法是如何使用它的。 –

@JimMischel：謝謝。你是對的，我在這裏沒有真正解釋它的代碼。我的查找程序仍舊從一個較舊的答案中找到，所以我只是用它。我已經添加了一個解釋。 –

在這裏，這種隱式堆表示確實非常合適。 –

IMO最有效的方法將與一個trie。這是一棵樹，每個節點最多有兩個兒子，一個用於.，另一個用於-，當這些字符可能在給定階段時。除了指向兒子的鏈接之外，節點還有一個「終端」字符，告訴從根節點到該節點的路徑是什麼字符;終端字符可以是零來表示路徑不編碼任何字符（字符串未完成）。

由於莫爾斯字母很小，所以您甚至可以手動構建字典。這是它的一部分。

. => E 
    . => I 
     . => S 
     - => U 
    - => A 
     . => R 
     - => W 
- => T 
    . => N 
     . => D 
     - => K 
    - => M 
     . => G 
     - => O

要利用此線索，寫一個遞歸函數，它接受作爲輸入的輸入流中的位置，並在字典樹的節點。如果節點具有終端字符，請將終端字符附加到輸出字符串，並將節點重置爲trie的根節點。同時，通過跟蹤與下一個輸入符號相匹配的兒子繼續探索trie。

這裏是爲數不多的第一步驟，在你的榜樣情況下，遞歸執行（前四個輸入符號的分析）：

. => E 
    .|. => EE 
     .|.|. => EEE 
      .|.|.|. => EEEE 
      .|.|.. => EEI 
     .|.. => EI 
      .|..|. => EIE 
      .|... => ES 
    .. => I 
     ..|. => IE 
      ..|.|. => IEE 
      ..|.. => II 
     ... => S 
      ...|. => SE 
      .... => H

來源

2016-01-25 09:43:56

你可以做2遍。首先將標記一個字母可能結束的位置，第二個將提取所有可能的字符串。

您可以將其作爲動態編程來實施。 possible[x]如果可以將第一個x字母解析爲某些字符，則爲true。您剔除possible[0] = true，然後計算所有其他x的值possible。要計算它，你需要最後的1,2,3和4個字符，如果它們匹配一些現有的莫爾斯碼，並且與字符串其餘部分相對應的可能值爲true，那麼標記possible[x]也是如此。這是O（N）。

現在你必須提取所有可能的單詞。所以，從最後開始，並使用possible向量來消除錯誤的解決方案。在這裏，你應該再次嘗試最後的1-4個字符，看看它們是否匹配，如果他們做的相應的possible位置是真的，那麼你把它作爲一個可能的字符，並遞歸調用該函數來產生剩下的所有解決方案。不幸的是，在最壞的情況下（當可能分區時）是指數O（4^N）。在實踐中，這將貫穿與輸入字符串匹配的可能詞的數量，所以如果只有少數選項，則該通過也將是快速的。

要注意，字符串越長，您就越有可能擁有更多選項和更多可能的解釋。

如果另外您將可能的單詞限制在預定義的集合中，則可以修改第一遍以使用單詞而不是單個字母。那麼可能的解釋數量應該會減少很多，即使在較長的字符串中，您的算法也會很快。

來源

2016-01-25 11:55:25 Sorin

莫爾斯沒有分隔符 - 最好的算法

回答

相關問題