Почти одинаковые названия

@kolay_ne · Регистрация: 07.03.2016

Студворк — интернет-сервис помощи студентам

Я нахожусь в папке А1. У нее есть несколько дочерних папок. Например, Б1, Б2, Б3. В каждой из них либо лежат файлы, либо еще папки В1, В2, в которых уже лежат файлы. Моя программа идет по всем этим папкам и копирует оттуда файлы *.mp3 в папочку А2. Раньше я делал это рекурсией,

Вот так

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
uses System.IO, util;
 
const
  s1 = 'C:\Музыка в подпапках';
  s2 = 'C:\Музыка в одной папке';
 
procedure abc(path: string);
begin
  var dir := new DirectoryInfo(path);
  var ins := dir.GetDirectories;
  execute('cmd', '/C copy "' + path + '\*.mp3" "' + s2 + '"');
  if(length(ins) > 0) then
    for i: integer := 0 to length(ins) - 1 do
    begin
      var s := path + '\' + ins[i].ToString;
      abc(s);
    end;
end;
 
begin
  abc(s1);
end.

, но потом мне объяснили, что это неправильно, и я стал делать

Вот так

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
uses System.IO, util;
 
const
  s1 = 'C:\Музыка в подпапках';
  s2 = 'C:\Музыка в одной папке';
 
begin
  var dir := new DirectoryInfo(s1);
  var res := dir.GetFiles('*.mp3', SearchOption.AllDirectories);
  for i: integer := 0 to length(res) - 1 do
  begin
    execute('cmd', '/C copy "' + res[i].FullName + '" "' + s2 + '"');
    a -= 1;
  end;
end.

Еще в программе я запоминаю, какие файлы скопировал и если в какой-то папке встретил еще раз файл с таким же именем, не копирую его. Вопрос вот в чем. Может быть, например, такое, что в двух разных папках у одинаковых файлов различаются 1-3 символа или не хватает 1-3 символов в названии одного файла по сравнению с другим. Где стоят различающиеся или отсутствующие символы, я не знаю. Как сделать так, чтобы файлы, у которых разница с уже скопированным 3 или меньше символов тоже не копировались? Для простоты давайте считать, что различающиеся или отсутствующие символы могут стоять только в начале, но буду очень благодарен, если покажете, как отследить их в любом месте... Как различающиеся символы сделать я примерно представляю, но вот отсутствующие в середине названия...

@volvo · 09.09.2017, 18:47

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

@kolay_ne · 09.09.2017, 19:43 **[ТС]**

Сообщение от volvo

посчитал

Как это сделать?Видимо, мне должна была помочь картинка, но я ее не понял... https://wikimedia.org/api/rest... d0183eec8c

@volvo · 09.09.2017, 20:41

На картинке - не самый эффективный рекурсивный способ вычисления:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function Dist(s1, s2: string): integer;
  
  function Levenshtein(s1: string; len_s1: integer; 
                       s2: string; len_s2: integer): integer;
  begin
    if Min(len_s1, len_s2) = 0 then 
      result := Max(len_s1, len_s2)
    else
      result := Arr(Levenshtein(s1, len_s1 - 1, s2, len_s2) + 1,
                    Levenshtein(s1, len_s1, s2, len_s2 - 1) + 1,
                    Levenshtein(s1, len_s1 - 1, s2, len_s2 - 1) + (s1[len_s1] = s2[len_s2] ? 0 : 1)).Min;
  end;
 
begin
  result := Levenshtein(s1, Length(s1), s2, Length(s2));
end;
 
begin
  writeln(Dist('sart', 'start')); // проверяем
end.

В англоязычной статье на Вики есть и коды для итеративного вычисления дистанции.

@kolay_ne · 09.09.2017, 22:55 **[ТС]**

volvo, Что-то не так. Вроде работает, но машина подсказывает непроходимые тесты:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function Dist(s1, s2: string): integer;
  
  function Levenshtein(s1: string; len_s1: integer; 
                       s2: string; len_s2: integer): integer;
  begin
    if Min(len_s1, len_s2) = 0 then 
      result := Max(len_s1, len_s2)
    else
      result := Arr(Levenshtein(s1, len_s1 - 1, s2, len_s2) + 1,
                    Levenshtein(s1, len_s1, s2, len_s2 - 1) + 1,
                    Levenshtein(s1, len_s1 - 1, s2, len_s2 - 1) + (s1[len_s1] = s2[len_s2] ? 0 : 1)).Min;
  end;
 
begin
  result := Levenshtein(s1, Length(s1), s2, Length(s2));
end;
 
begin
  writeln(Dist('01. ночь.mp3', '02. хоровод.mp3')); //Берет и вешается
end.

Добавлено через 1 час 9 минут
volvo, Взял готовую реализацию с википедии. Она не шибко красивая, но норм работает. Завтра попробую покрасивее сделать путем перевода с python...

@volvo · 10.09.2017, 00:17

Сообщение от kolay_ne

//Берет и вешается

Ну я же написал:

Сообщение от volvo

не самый эффективный рекурсивный способ вычисления

Значит, возьмем и сделаем его более эффективным (при помощи запоминания промежуточных результатов вместо их многократного пересчета - то есть, мемоизации). Итого имеем:

Pascal
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
function Dist(s1, s2: string): integer;
 
  var m : array [,] of integer;
  
  function Levenshtein(len_s1: integer; 
                       len_s2: integer): integer;
                       
    function Check(ix1, ix2 : integer) : integer;
    begin
      if m[ix1, ix2] = -1 then m[ix1, ix2] := Levenshtein(ix1, ix2);
      result := m[ix1, ix2];
    end;
    
  begin
    if Min(len_s1, len_s2) = 0 then result := Max(len_s1, len_s2)
    else
    begin
      m[len_s1, len_s2] := Arr(Check(len_s1 - 1, len_s2) + 1,
                               Check(len_s1, len_s2 - 1) + 1,
                               Check(len_s1 - 1, len_s2 - 1) + (s1[len_s1] = s2[len_s2] ? 0 : 1)).Min;
      result := m[len_s1, len_s2];
    end;
  end;
 
begin
  m := MatrFill(length(s1) + 1, length(s2) + 1, -1);
  result := Levenshtein(Length(s1), Length(s2));
end;
 
begin
  writeln(Dist('01. ночь длинный текст_проверка .mp3', '02. хоровод длинный текст_проверка .mp3')); // результат возвращается мгновенно
end.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

Почти одинаковые названия

Решение

Решение

@volvo Супер-модератор 33378 / 21502 / 8236 Регистрация: 22.10.2011 Сообщений: 36,899 Записей в блоге: 11
	09.09.2017, 18:47
	Сообщение было отмечено kolay_ne как решение Решение Я бы посчитал расстояние Левенштейна между этими названиями, оно как раз и выдаст количество различающихся/недостающих букв. Проверить онлайн, что будет выдано, перед тем, как начинать программировать вычисление дистанции, можно здесь 2