Разбор азбуки Морзе

Я пытаюсь решить эту проблему. Цель состоит в том, чтобы определить количество способов интерпретации строки Морзе с учетом словаря слов. Что я сделал, так это то, что я сначала «перевел» слова из моего словаря на Морзе. Затем я использовал наивный алгоритм, ища все способы его рекурсивной интерпретации.

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <iterator>
using namespace std;

string morse_string;
int morse_string_size;
map<char, string> morse_table;
unsigned int sol;

void matches(int i, int factor, vector<string> &dictionary) {
    int suffix_length = morse_string_size-i;
    if (suffix_length <= 0) {
        sol += factor;
        return;
    }
    map<int, int> c;
    for (vector<string>::iterator it = dictionary.begin() ; it != dictionary.end() ; it++) {
        if (((*it).size() <= suffix_length) && (morse_string.substr(i, (*it).size()) == *it)) {
            if (c.find((*it).size()) == c.end())
                c[(*it).size()] = 0;
            else
                c[(*it).size()]++;
        }
    }

    for (map<int, int>::iterator it = c.begin() ; it != c.end() ; it++) {
        matches(i+it->first, factor*(it->second), dictionary);
    }
}

string encode_morse(string s) {
    string ret = "";
    for (unsigned int i = 0 ; i < s.length() ; ++i) {
        ret += morse_table[s[i]];
    }
    return ret;
}

int main() {
    morse_table['A'] = ".-"; morse_table['B'] = "-..."; morse_table['C'] = "-.-."; morse_table['D'] = "-.."; morse_table['E'] = "."; morse_table['F'] = "..-."; morse_table['G'] = "--."; morse_table['H'] = "...."; morse_table['I'] = ".."; morse_table['J'] = ".---"; morse_table['K'] = "-.-"; morse_table['L'] = ".-.."; morse_table['M'] = "--"; morse_table['N'] = "-."; morse_table['O'] = "---"; morse_table['P'] = ".--."; morse_table['Q'] = "--.-"; morse_table['R'] = ".-."; morse_table['S'] = "..."; morse_table['T'] = "-"; morse_table['U'] = "..-"; morse_table['V'] = "...-"; morse_table['W'] = ".--"; morse_table['X'] = "-..-"; morse_table['Y'] = "-.--"; morse_table['Z'] = "--..";
    int T, N;
    string tmp;
    vector<string> dictionary;
    cin >> T;

    while (T--) {
        morse_string = "";
        cin >> morse_string;
        morse_string_size = morse_string.size();
        cin >> N;
        for (int j = 0 ; j < N ; j++) {
            cin >> tmp;
            dictionary.push_back(encode_morse(tmp));
        }

        sol = 0;
        matches(0, 1, dictionary);
        cout << sol;

        if (T)
            cout << endl << endl;
    }

    return 0;
}

Теперь дело в том, что у меня есть только 3 секунды времени выполнения, и мой алгоритм не будет работать при этом ограничении времени.

Это хороший способ сделать это, и если да, то что мне не хватает? В противном случае, можете ли вы дать несколько советов о том, что является хорошей стратегией?

РЕДАКТИРОВАТЬ: В словаре может быть не более 10 000 слов и не более 1000 символов в строке Морзе.


parsing morse-code algorithm
person Community    schedule 14.05.2014    source источник
comment
И извините, я не поздоровался, редактирование не работает, и я слишком быстро нажал Enter :/   -  person    schedule 15.05.2014
comment
Этот вопрос не относится к теме StackOverflow, поскольку CodeReview лучше подходит для проверки/оптимизации рабочего кода.   -  person Jongware    schedule 15.05.2014
comment
Я бы лично сказал, что это было по теме здесь. Дело не в коде, а в алгоритме, стоящем за кодом, и алгоритмы кажутся мне актуальными. Просто мои мысли.   -  person Chris    schedule 15.05.2014
comment
@HighPerformanceMark: проблема признает это, и я думаю, что вопрос гораздо лучше сформулировать как практическую проблему с азбукой Морзе, чем если бы он использовал произвольные строки из единиц и нулей с некоторыми произвольными допустимыми символами, составленными из них. В общем, не критикуйте то, как другие люди проводят свое время.   -  person Chris    schedule 15.05.2014
comment
Похоже на проблему динамического программирования.   -  person fgb    schedule 15.05.2014
comment
Интересная проблема. Вы можете создать trie из словаря фраз. Тогда это просто вопрос чтения каждой точки/тире и обхода дерева. Это было бы очень быстро, при условии, что словарь не огромен.   -  person Jim Mischel    schedule 15.05.2014
comment
@JimMischel: я думал об этом, но словарь может содержать до 10 000 слов (я отредактировал свой пост, чтобы уточнить это).   -  person    schedule 15.05.2014
comment
10 000 — это немного.   -  person Adam    schedule 15.05.2014

Ответы (1)


arrow_upward
0
arrow_downward

Решение, сочетающее динамическое программирование с скользящим хешем, должно работать для решения этой проблемы.

Начнем с простого решения для динамического программирования. Мы выделяем вектор, который мы будем использовать для хранения известных счетчиков для префиксов morse_string. Затем мы перебираем morse_string и в каждой позиции перебираем все слова и оглядываемся назад, чтобы посмотреть, могут ли они вписаться в morse_string. Если они подходят, мы используем вектор динамического программирования, чтобы определить, сколько способов мы могли бы построить префикс от morse_string до i-dictionaryWord.size().

vector<long>dp;
dp.push_back(1);
for (int i=0;i<morse_string.size();i++) {
   long count = 0;
   for (int j=1;j<dictionary.size();j++) {
       if (dictionary[j].size() > i) continue;
       if (dictionary[j] == morse_string.substring(i-dictionary[j].size(),i)) {
           count += dp[i-dictionary[j].size()];
       }
   }
   dp.push_back(count);
}
result = dp[morse_code.size()]

Проблема этого решения в том, что оно слишком медленное. Предположим, что N — это длина morse_string, а M — это размер dictionary, а K — это размер самого большого слова в словаре. Он выполнит O(N*M*K) операций. Если мы предположим, что K=1000 это примерно 10^10 операций, что слишком медленно для большинства машин.

Стоимость K пришла из строки dictionary[j] == morse_string.substring(i-dictionary[j].size(),i)

Если бы мы могли ускорить сопоставление строк до постоянной или логарифмической сложности, все было бы в порядке. Вот тут и приходит на помощь скользящее хеширование. Если вы создаете скользящий хеш-массив из morse_string, то идея состоит в том, что вы можете вычислить хэш любой подстроки morse_string в O(1). Таким образом, вы могли бы сделать hash(dictionary[j]) == hash(morse_string.substring(i-dictionary[j].size(),i))

Это хорошо, но при наличии несовершенного хеширования у вас может быть несколько слов из словаря с одним и тем же хешем. Это означало бы, что после получения совпадения хэша вам все равно нужно будет сопоставлять строки, а также хэши. В соревнованиях по программированию люди часто предполагают идеальное хеширование и пропускают сопоставление строк. Часто это безопасная ставка, особенно для небольшого словаря. В случае, если он не дает идеального хеширования (что вы можете проверить в коде), вы всегда можете немного изменить свою хеш-функцию, и, возможно, скорректированная хеш-функция даст идеальное хеширование.

person cyon    schedule 15.05.2014
comment
Динамическое программирование было действительно правильным подходом. Однако мое решение не использует скользящий хеш и прошло тесты. Я никогда не слышал о прокатке гашиша, поэтому спасибо за ваше предложение, сегодня я кое-чему научился! - person ; 16.05.2014
comment
@ user3638414 Не за что. Я думал, что просто динамическое программирование будет слишком медленным, но, похоже, я ошибался. Преждевременная оптимизация :) - person cyon; 16.05.2014