Форум программистов, компьютерный форум, киберфорум
Java
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.71/35: Рейтинг темы: голосов - 35, средняя оценка - 4.71
31 / 31 / 6
Регистрация: 11.07.2013
Сообщений: 241

Поиск анаграмм в файле

29.11.2013, 04:13. Показов 6774. Ответов 12
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте! Такая задача:
Есть входной текстовой файл, в нем слова(какие попало и написаны как попало, а не красиво через пробел).
Нужно в другой текстовый файл записать все найденные анаграммы(из одних и тех же букв, одинаковая длина, каждая буква 1 раз, регистр не учитывается): одна строка - одна группа анаграмм

Пример:

Вход: Мама дай мне меН йад
Выход:

дай йад
мне меН


Учитывая, что размер входного файла может быть большим и даже очень большим, хорошая ли идея:

-Завести хешмапу <String, List<String>>, где String - слово, List<String> список всех анаграм для этого слова, включая его самого

-Прочитать файл до конца, заполнив эту мапу

-Переписывать из мапы в другой файл, если длина листа > 1

?


Может подскажете другую идею.
Спасибо
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
29.11.2013, 04:13
Ответы с готовыми решениями:

Поиск слова в файле
Задача найти все &quot;public&quot; и заменить на &quot;private&quot; и подсчитать сколько пабликов в файле. Найти , нашёл. А вот сколько их понять не могу...

Поиск ссылок в HTML файле
Здравствуйте! Возникла такая задача: на вход поступает url, идет по нему переход, в полученной странице(в виде HTML) ищутся все...

Поиск в файле
Поиск в файлах разных типов, разной структуры с разным результатом(разные файлы). Разного размера. Может кто посоветует в какую...

12
3176 / 1935 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
29.11.2013, 06:13
список всех анаграм для этого слова, включая его самого
Факториал от длины слова. И даже без учета повторов, все равно, слишком много.
Составьте, к примеру, список для "никотинамидадениндинуклеотидфосфатгидрин"

Задается словарь. Найти в нем все анаграммы
0
31 / 31 / 6
Регистрация: 11.07.2013
Сообщений: 241
29.11.2013, 06:56  [ТС]
Цитата Сообщение от gazlan Посмотреть сообщение
Факториал от длины слова.
Простите, не понял. Что будет факториал?

Добавлено через 1 минуту
Цитата Сообщение от gazlan Посмотреть сообщение
Составьте, к примеру, список для "никотинамидадениндинуклеотидфосфатгидри н"
Какой список? Список всех анаграм из групы, где есть слово никотинамидадениндинуклеотидфосфатгидрин ?

Добавлено через 3 минуты
Цитата Сообщение от gazlan Посмотреть сообщение
Составьте, к примеру, список для "никотинамидадениндинуклеотидфосфатгидри н"
дак в файле может вообще не быть анаграмм к этому слову
или я вас не понимаю
0
3176 / 1935 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
29.11.2013, 07:07
Цитата Сообщение от OxomHuK Посмотреть сообщение
или я вас не понимаю
Не понимаете. Смотрите алго по ссылке.
0
31 / 31 / 6
Регистрация: 11.07.2013
Сообщений: 241
29.11.2013, 07:27  [ТС]
вот я набросал код

Добавлено через 11 секунд
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintWriter;
import java.util.*;
 
 
public class FindAnagram {
 
    private boolean areAnagrams(String word1, String word2) {
        if (word1 == null || word2 == null || word1.length() != word2.length())
            return false;
        char[] ch1 = word1.toLowerCase().toCharArray();
        char[] ch2 = word2.toLowerCase().toCharArray();
        Arrays.sort(ch1);
        Arrays.sort(ch2);
        return Arrays.equals(ch1, ch2);
    }
 
    private boolean contains(Map<String, HashSet<String>> map, String word) {
        Set<String> keysSet = map.keySet();
        for (String key : keysSet) {
            if (areAnagrams(key, word))
                return true;
        }
        return false;
    }
 
    private String keyForAnagram(Map<String, HashSet<String>> map, String anagram) {
        Set<String> keysSet = map.keySet();
        for (String key : keysSet) {
            if (areAnagrams(key, anagram))
                return key;
        }
        return null;
    }
 
    public void findAnagrams(File from, File to) throws FileNotFoundException {
        Map<String, HashSet<String>> map = new HashMap<String, HashSet<String>>();
        Scanner sc = new Scanner(from, "Cp1251");
        PrintWriter out = new PrintWriter(new FileOutputStream(to));
 
        //чтение из файла в map
        while (sc.hasNextLine()) {
            String line = sc.nextLine();
           // String[] words = line.split("\\s+");
            String[] words = line.split("[,;:.!?\\s]+");
 
            for (String word : words) {
                if (!contains(map, word)) {
                    map.put(word, new HashSet<String>());
                    HashSet<String> set = map.get(word);
                    set.add(word);
 
                } else {
                    String key = keyForAnagram(map, word);
                    HashSet<String> set = map.get(key);
                    set.add(word);
                }
            }
        }      
 
        //запись из map в другой файл
        Set<String> keys = map.keySet();
        for (String key : keys) {
            if (map.get(key).size() > 1) {
                Set<String> anagrams = map.get(key);
                for (String anagram : anagrams) {
                    out.print(anagram + " ");
                }
                out.println();
            }
        }
        sc.close();
        out.close();
    }
 
    public static void main(String[] args) {
        try {
        File from = new File("C:\\file_from.txt");
        File to = new File("C:\\file_to.txt");
        new FindAnagram().findAnagrams(from, to);
        } catch(FileNotFoundException e) {
            System.out.println("File not found " + e.getMessage());
        }
    }
}
Добавлено через 1 минуту
вы мне обьясните, пожалуйста, почему так как у меня плохо(в каком конкретно месте)

Добавлено через 1 минуту
еще вопрос: из файла все слова нужно же куда то сохранять в память, правильно? Не map дак list
0
3176 / 1935 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
29.11.2013, 07:37
Цитата Сообщение от OxomHuK Посмотреть сообщение
Код Java(TM)
На Джаве не пишу и читать не люблю. Так что, могу понять неверно. Дождитесь комментариев тех, кто знает этот язык лучше.
0
31 / 31 / 6
Регистрация: 11.07.2013
Сообщений: 241
29.11.2013, 08:00  [ТС]
скачал я ради интереса мастера и маргариту ~ 0.8M, запустил прогу, читала/записывала минут 10, это долго?
0
 Аватар для verylazy
462 / 462 / 71
Регистрация: 26.02.2013
Сообщений: 1,263
29.11.2013, 10:44
Лучший ответ Сообщение было отмечено как решение

Решение

Дошел вчера пешком до работы за 35 минут, это долго?
3
31 / 31 / 6
Регистрация: 11.07.2013
Сообщений: 241
29.11.2013, 22:45  [ТС]
Цитата Сообщение от verylazy Посмотреть сообщение
Дошел вчера пешком до работы за 35 минут, это долго?

Не по теме:

понял :D

0
3176 / 1935 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
30.11.2013, 02:14
минут 10, это долго?
Долго.

Интереса ради, написал на С с сохранением промежуточных результатов на диск. Скачал M&M, конвертировал в Win-1251 (~747 Kb), обрабатывается примерно 10 сек по наручным часам. Если не использовать диск, а держать все в памяти, скорость должна вырасти минимум на порядок.
Миниатюры
Поиск анаграмм в файле  
Вложения
Тип файла: 7z Булгаков.txt.7z (3.0 Кб, 7 просмотров)
Тип файла: 7z Anagrammer.7z (11.8 Кб, 23 просмотров)
1
31 / 31 / 6
Регистрация: 11.07.2013
Сообщений: 241
30.11.2013, 07:43  [ТС]
да, свою ошибку с алгоритмом я понял, переделываю на другой

Добавлено через 51 минуту
А подскажите пожалуйста, как из ArrayList<Parser> list1 получить ArrayList<ArrayList<String>>,

где
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Arrays;
 
public class Parser {
    private String word;
    private String signature;
 
    public Parser(String word) {
        this.word = word;
        char[] wordToCharArray = word.toLowerCase().toCharArray();
        Arrays.sort(wordToCharArray);
        signature = new String(wordToCharArray);
    }
 
    public String getWord() {
        return word;
    }
 
    public String getSignature() {
        return signature;
    }
}
То есть, есть список обьектов, каждый из которых хранит слово и строку, которая = это же слово, отсортированное по буквам
Этот список list 1 отсортирован вот по этим строкам

Например:
list1 = {(pans, aups), (snap, aups), (pots, opst), (stop, opst), (tops, opst), (opt, opt)}

Как мне из него получить список списков строк(списков анаграм), то есть:

list2 = {<pans, snap>, <pots, stop, tops>}
// если для слова не нашлась анаграмма в list1 то его не нужно заносить в список list2

Спасибо

Добавлено через 59 минут
разобрался, переписал алгоритм, теперь для 1М работает за 1 секундку....

Не по теме:

а было 10 минут:-[



Добавлено через 3 часа 12 минут
задам еще вопрос:
когда я читаю из файла(предположим 10М ~1_000_000 слов) в память и использую сканер
Java
1
2
3
4
5
6
7
8
9
10
 List<String> listOfWords = new ArrayList<String>();
 
        Scanner scanner = new Scanner(source, "UTF-8");
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine();
            String[] words = line.split("[()…»«,;:.!?\\s]+");
            for (String word : words) {
                listOfWords.add(word);
            }
        }
то:
это(сканер а не допустим BufferedReader) нормально в принципе
это нормально только учитывая небольшой размер файла

ну то есть, при чтении очень большого файла(ну пускай аж до 1Г) сканером нормально пользоваться или есть альтернативы лучше?(подскажите)
0
3176 / 1935 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
30.11.2013, 10:15
при чтении очень большого файла
IMHO, неверно привязывать сканер к контейнеру - это разные сущности.

Сканер должен просматривать входной поток и выдавать очередную лексему (при необходимости, вместе с ее позицией в потоке и размером). Все. Внутреннее устройство файла (и есть ли там вообще "строки") не имеет значения - точно так же, на вход программы можно подать EXE-файл.

C++
1
2
3
4
5
6
7
   while (Length = GetWord())
   {
      if ((Length >= Min) && (Length <= Max))
      {
         // Insert Word into DB
      }
   }
Где хранить полученный список лексем - вопрос реализации, никак не связанный с разбором текста. У меня, например, это (собственная) On Disk Key-Value DB (B*Tree). С тем же успехом, это может быть любая реляционная DB - для (очень) больших файлов или In Memory DB для игрушечных задач.

Впрочем, для естественного языка можно ожидать словарь порядка 100,000 уникальных слов даже для произвольно больших файлов и, если при вставке в DB сразу проверять дубликаты, то, ценой некоторого замедления, вполне можно хранить все в RAM (считая среднюю длину слова 10 байт (не Unicode), это всего 1 Mb нетто).
Миниатюры
Поиск анаграмм в файле  
1
3176 / 1935 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
30.11.2013, 22:42
Музыкой навеяло.

Словарь русских анаграмм. Составлен по большому (3,032,693) словарю лексем. В файле lexicon.469979.txt содержится отсортированный по алфавиту список всех уникальных слов. Может быть использован для быстрого просмотра/поиска. Если слово есть в лексиконе, то к нему существует анаграмма.

Ex: ЯЩЕРИЦА -- ЦАРЯЩИЕ
Вложения
Тип файла: 7z anagrams.russian.7z (1.97 Мб, 38 просмотров)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
30.11.2013, 22:42
Помогаю со студенческими работами здесь

Поиск в файле
Найти в файле числа

Поиск слова в файле
Доброго времени суток. Мне нужно из текстового файла найти заданное слово и вывести его в консоль. Я написал примерный код, но слово...

Поиск слова в файле
Написать программу для поиска слова в файле, программа должна показать: количество таких слов в файле, для каждого найденного слова: номер...

Поиск чисел в текстовом файле
Нужно найти самое большое число в каждой строчке текстового файла и вывести их.

Поиск слова в текстовом файле
Разработать программу, которая читает текстовый файл и некоторое слово и выводит те строки файла, которые содержат данное слово. Имя...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Новые блоги и статьи
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии
Hrethgir 01.03.2026
Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten
8Observer8 27.02.2026
Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru