Преобразование азбуки Морзе в словарь английского языка

Question

Я пытаюсь решить проблему, связанную с тем, что по строке символов азбуки Морзе найти значимые слова в словаре

Например

Эта входная строка "..-. ---- ..-.-... --- ..-.--" должна переводиться как "fox lazy", возможны несколько других переводов, но это одно из возможных решений, поскольку эти два слова присутствуют в словаре английского языка.

Я написал 2 функции, TranslateMorse и SegmentString. SegmentString разбивает английскую строку и находит все значимые слова в словаре. Например, если input «foxlazy», функция может найти «fox» и «lazy» - это два значащих слова, присутствующих в словаре.

TranslateMorse должен фактически преобразовать ввод кода Морзе "..-. ---- ..-.-... --- ..-.--" в "foxlazy", чтобы SegmentString выдавал результирующий вывод , но сложная часть заключается в том, что перевод MorseCode не является простым и дает мне много переводов.

Как мне решить эту проблему?

import java.util.*;

public class MorseCode {
    String TranslateMorse(String input, Map<String, String> morse) {
        // "-.-..-.--..--...-....---"
        if (morse.containsKey(input))
            return morse.get(input);
        int len = input.length();
        for (int i = 1; i < len; i++) {
            String prefix = input.substring(0, i);
            if (morse.containsKey(prefix)) {
                String suffix = input.substring(i, len);
                String segSuffix = SegmentString(suffix, morse);
                if (segSuffix != null) {
                    return morse.get(prefix) + segSuffix;
                }
            }
        }
        return null;
    }

    String SegmentString(String input, Set<String> dict) {
        if (dict.contains(input))
            return input;
        int len = input.length();
        for (int i = 1; i < len; i++) {
            String prefix = input.substring(0, i);
            if (dict.contains(prefix)) {
                String suffix = input.substring(i, len);
                String segSuffix = SegmentString(suffix, dict);
                if (segSuffix != null) {
                    return prefix + " " + segSuffix;
                }
            }
        }
        return null;
    }

    // Driver method
    public static void main(String args[]) {
        Map<String, String> morse = new HashMap<>();
        morse.put(".-", "a");
        morse.put("-...", "b");
        morse.put("-.-.", "c");
        morse.put("-..", "d");
        morse.put(".", "e");
        morse.put("..-.", "f");
        morse.put("--.-", "g");
        morse.put("....", "h");
        morse.put("..", "i");
        morse.put(".---", "j");
        morse.put("-.-", "k");
        morse.put(".-..", "l");
        morse.put("--", "m");
        morse.put("-.", "n");
        morse.put("---", "o");
        morse.put(".--.", "p");
        morse.put("--.-", "q");
        morse.put(".-.", "r");
        morse.put("...", "s");
        morse.put("-", "t");
        morse.put("..-", "u");
        morse.put("...-", "v");
        morse.put(".--", "w");
        morse.put("-..-", "x");
        morse.put("-.--", "y");
        morse.put("--..", "z");

        Set<String> dict = new HashSet<>();
        dict.add("apple");
        dict.add("honey");
        dict.add("fox");
        dict.add("quick");
        dict.add("jumped");
        dict.add("bill");
        dict.add("jam");
        dict.add("holy");
        dict.add("mega");
        dict.add("lazy");
        // fox lazy
        String input = "..-.----..-.-...---..-.--";
        MorseCode m = new MorseCode();
        String alpha = m.TranslateMorse(input, morse);
        System.out.println(alpha);
        System.out.println(m.SegmentString(alpha, dict));
    }
}

Answer 1

Я предполагаю, что смысл этой проблемы в том, что в потоке азбуки Морзе нет ни буквы, ни слова, ни разделителей (пробелов), и это является частью анализа.Ключевые проблемы, которые я вижу с вашим кодом:

• Вы предполагаете, что получите один ответ, отраженный в выборе типов данных, когда на самом деле вы собираетесьполучите несколько ответов, которые необходимо отфильтровать.

• Ваш TranslateMorse() метод вызывает SegmentString(), когда он должен вызывать себя рекурсивно!

Ниже моя переделка вашего кода, которая решает эти две проблемы:

import java.util.*;

public class MorseCode {

    List<String> TranslateMorse(String input, Map<String, String> dictionary) {
        List<String> strings = new ArrayList<String>();

        if (dictionary.containsKey(input)) {
            strings.add(dictionary.get(input));
        }

        int length = input.length();

        for (int i = 1; i < length; i++) {
            String prefix = input.substring(0, i);

            if (dictionary.containsKey(prefix)) {
                String suffix = input.substring(i, length);
                List<String> translations = TranslateMorse(suffix, dictionary);

                if (! translations.isEmpty()) {
                    String letter = dictionary.get(prefix);

                    for (String translation : translations) {
                        strings.add(letter + translation);
                    }
                }
            }
        }

        return strings;
    }

    List<String> SegmentString(String input, Set<String> wordList) {
        List<String> strings = new ArrayList<String>();

        if (wordList.contains(input))
            strings.add(input);

        int length = input.length();

        for (int i = 1; i < length; i++) {
            String prefix = input.substring(0, i);

            if (wordList.contains(prefix)) {
                String suffix = input.substring(i, length);
                List<String> expansions = SegmentString(suffix, wordList);

                if (! expansions.isEmpty()) {
                    for (String expansion : expansions) {
                        strings.add(prefix + " " + expansion);
                    }
                }
            }
        }

        return strings;
    }

    public static void main(String args[]) {
        Map<String, String> morse = new HashMap<>();

        morse.put(".-", "a");
        morse.put("-...", "b");
        morse.put("-.-.", "c");
        morse.put("-..", "d");
        morse.put(".", "e");
        morse.put("..-.", "f");
        morse.put("--.-", "g");
        morse.put("....", "h");
        morse.put("..", "i");
        morse.put(".---", "j");
        morse.put("-.-", "k");
        morse.put(".-..", "l");
        morse.put("--", "m");
        morse.put("-.", "n");
        morse.put("---", "o");
        morse.put(".--.", "p");
        morse.put("--.-", "q");
        morse.put(".-.", "r");
        morse.put("...", "s");
        morse.put("-", "t");
        morse.put("..-", "u");
        morse.put("...-", "v");
        morse.put(".--", "w");
        morse.put("-..-", "x");
        morse.put("-.--", "y");
        morse.put("--..", "z");

        Set<String> english = new HashSet<>();

        english.add("apple");
        english.add("honey");
        english.add("fox");
        english.add("quick");
        english.add("jumped");
        english.add("bill");
        english.add("jam");
        english.add("holy");
        english.add("mega");
        english.add("lazy");

        String input = "..-.----..-.-...---..-.--"; // fox lazy
        MorseCode decoder = new MorseCode();
        List<String> decodings = decoder.TranslateMorse(input, morse);

        for (String decoding : decodings) {
            List<String> phrases = decoder.SegmentString(decoding, english);

            for (String phrase : phrases) {
                System.out.println(input + " -> " + decoding + " -> " + phrase);
            }
        }
    }
}

ИСПОЛЬЗОВАНИЕ

> java MorseCode
..-.----..-.-...---..-.-- -> foxlazy -> fox lazy
>

Это не быстрая программа - она ​​занимает около10 секунд в этом примере, поскольку он должен отфильтровать все возможные интерпретации цифр и знаков в символах азбуки Морзе, а затем отфильтровать их по списку английских слов.