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

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

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

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

Вот так

Pascal

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

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

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

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

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.

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

Решение

Решение

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

@kolay_ne 16 / 18 / 11 Регистрация: 07.03.2016 Сообщений: 362
	09.09.2017, 19:43 [ТС]	3
	Сообщение от volvo посчитал Как это сделать?Видимо, мне должна была помочь картинка, но я ее не понял... https://wikimedia.org/api/rest... d0183eec8c 0

	10.09.2017, 00:17