Как искать строку в заданном текстовом файле на другом языке - PullRequest
0 голосов
/ 27 июня 2018

Я хочу разработать алгоритм поиска по шаблону для приложения музыкальной системы, которое ищет данное ключевое слово и воспроизводит музыку, текстовый файл которой содержит данное ключевое слово. Сейчас существует множество алгоритмов поиска по шаблону, которые могут сделать это эффективно (например, KMP, хеширование (может привести к ошибке) и т. Д.). Но моя главная проблема заключается в том, что вся база данных на другом языке (не говоря уже о хинди). Теперь пользователь вводит данное ключевое слово на языке "хинди", и я хочу выполнить поиск в базе данных, которая также содержит язык "хинди". Моя главная задача заключается в том, как эффективно осуществлять поиск в этой базе данных?

Я думаю, что мы не можем сделать алгоритм KMP для неанглийского языка, потому что используемые нами символы ascii содержат только английские алфавиты и другие числовые буквы, но не содержат букв другого языка. Поэтому, пожалуйста, скажите мне, как я могу продолжить, так как я не могу найти решение, или скажите, где я ошибаюсь?

1 Ответ

0 голосов
/ 27 июня 2018

Алгоритм KMP не основан на алфавите, он использует символы из данного шаблона и текста. Более того, в таких языках, как Java, строки используют кодировку UTF-8, поэтому вы можете использовать любой язык, который вам нравится, и алгоритм будет работать правильно, в других вам нужно явно выбрать кодировку. Здесь я даю ссылку на пример на Ideone использования KMP с не ascii charset. алгоритм KMP

    /* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone {
    int[] f;
    public void dfa(String pattern) {
        int m = pattern.length();
        f = new int[m+1];
        f[0] = 0;
        f[1] = 0;
        for(int i=2; i<=m; i++) {
            int j = f[i-1];
            for(;;) {
                if(pattern.charAt(j) == pattern.charAt(i-1)) {
                    f[i] = j +1;
                    break;
                }
                if(j==0) {
                    f[i] = 0;
                    break;
                }
                j = f[j];
            }
        }
    }

    public int match(String text, String pattern) {
        dfa(pattern);
        int n = text.length();
        int m = pattern.length();
        int i = 0;
        int j = 0;
        for(;;) {
            if(i == n) break;
            if(text.charAt(i) == pattern.charAt(j)) {
                j++;
                i++;
                if(j == m) return i;
            }
            else if(j > 0) j =f[j];
            else i++;
        }
        return -1;
    }

    public static void main(String[] args) {
        Ideone kmp = new Ideone();
        String text = "AĄĘĆABA";
        String pattern = "ĄĘĆ";
        System.out.println(kmp.match(text, pattern));
    }
}
...