正则表达式，从分隔字符串中删除重复路径

Question

我将尝试使用正则表达式从分号分隔的字符串中删除重复的文件路径。 最终路径的顺序无关紧要。

示例输入：

C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path5;C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path6;C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path3;C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path3;

期望的输出结果：

C:\Users\user\Desktop\TESTING\path5;C:\Users\user\Desktop\TESTING\path6;C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path3;

我有以下正则表达式，虽然有效但在输入字符串很长时非常缓慢。再加上对成千上万行运行它，所需的时间很糟糕。

\b([^;]+)(?=.*;\1;);

任何提高此内容性能的建议都将不胜感激！

- Troy Harter

---

路径的顺序重要吗？ - haukex

不，只是要删除重复项。 - Troy Harter

将字符串按分号拆分，并在获取的数组上运行某个版本的unique函数。这个程序是用C#还是Perl编写的？ - zdim

Perl还是C#？@TroyHarter - revo

选择仅选择最后一次出现，然后使用替换是一个选项吗？ - The fourth bird

Answer 1

或者是C#版本：

using System;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        var paths = @"C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path5;C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path6;C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path3;C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path3;";

        var cleaned = string.Join(";", new HashSet<string>(paths.Split(';')));

        Console.WriteLine(cleaned);
    }
}

输出:

C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path5;C:\Users\user\Desktop\TESTING\path6;C:\Users\user\Desktop\TESTING\path3;

将输入在 ; 处分割，使用 HashSet<string>(..) 去除重复项，再次使用 ; 进行连接。

---

注意: 如果您的路径包含目录名称中的 ;，则此方法将无效 - 您需要更有创意地解决该问题 - 但对于任何您使用的正则表达式也是如此。

- Patrick Artner

Answer 2

使用哈希表是Perl中去重的典型方式。还可以参考perlfaq4: How can I remove duplicate elements from a list or array?。

my $str = q{C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path5;C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path6;C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path3;C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path3};
my %seen;
my $out = join ';', sort grep { !$seen{$_}++ } split /;/, $str;
print $out, "\n";
__END__
# Output:
C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path3;C:\Users\user\Desktop\TESTING\path5;C:\Users\user\Desktop\TESTING\path6

我在这里加入了sort，但如果您不需要它，可以将其删除。

虽然您还没有指定实现是应该使用C#还是Perl，但相同的想法也适用于C#。（更新：请参见Patrick Artner的答案）

请注意，正则表达式很慢，因为对于每个匹配项\b([^;]+)，引擎必须扫描整个字符串的其余部分以查找前瞻.*;\1;，因此基本上就像有嵌套循环一样。

- haukex

Answer 3

我认为使用Perl的哈希表习惯用法更容易实现。请看以下示例：

@items = (1,2,4,1,1,1);

my %uniq;
undef @uniq{ @items };
my @uniques = keys %uniq;

print join " ",@uniques

输出：

1 2 4

每个键在哈希表中仅存在一次，将相同的键分配给哈希表多次只会存储与该键相关的最新值。这种行为有优点！例如，要查找列表的唯一元素：

使用哈希切片和 undef 将哈希表的值设置为 undef。这个习惯用法是使用哈希表执行集合操作的最便宜的方法。

以上内容摘自书籍Modern perl books，以下是链接供您查看。哈希表习惯用法 我们可以清楚地看到，在您的情况下可以利用它。

use feature "say";

my $sample_text= C:\Users\user\Desktop\TESTING\path3;C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path3;;

#Split the paths seperated by ';' into an array of paths 
my @path_arr=  split /;/,$sample_text;

say "Path files with duplicates";
print join "\n",@path_arr;
print "------------------------";

my %temp_hash;                     } THIS 
undef @temp_hash{@path_arr};       }    IS WHAT 
my @unique  = keys %temp_hash;     }       YOU WANT

say "Path files without duplicates";

print join "\n",@unique;

输出：

Path files with duplicates:
C:\Users\user\Desktop\TESTING\path1
C:\Users\user\Desktop\TESTING\path5
C:\Users\user\Desktop\TESTING\path1
C:\Users\user\Desktop\TESTING\path6
C:\Users\user\Desktop\TESTING\path1
C:\Users\user\Desktop\TESTING\path3
C:\Users\user\Desktop\TESTING\path1
C:\Users\user\Desktop\TESTING\path3
-----------------------------
Path files without duplicates:
C:\Users\user\Desktop\TESTING\path1
C:\Users\user\Desktop\TESTING\path3
C:\Users\user\Desktop\TESTING\path6
C:\Users\user\Desktop\TESTING\path5

我相信这是实现你想要的最快捷的方式。如果性能是一个问题。

- void

Answer 4

尝试以下代码。

var inputStr = "C:\\Users\\user\\Desktop\\TESTING\\path1;C:\\Users\\user\\Desktop\\TESTING\\path5;C:\\Users\\user\\Desktop\\TESTING\\path1;C:\\Users\\user\\Desktop\\TESTING\\path6;C:\\Users\\user\\Desktop\\TESTING\\path1;C:\\Users\\user\\Desktop\\TESTING\\path3;C:\\Users\\user\\Desktop\\TESTING\\path1;C:\\Users\\user\\Desktop\\TESTING\\path3"

var urlArr = inputStr.split(";");
var uniqueUrlList = [];

urlArr.forEach(function (elem, indx1) {
    let foundElem = uniqueUrlList.find((x, indx2)=>{
        return x.toUpperCase() === elem.toUpperCase() &&
        (indx1 != indx2);
    });    
    
    if (foundElem === undefined) {
        uniqueUrlList.push(elem);
    }
});

console.log(uniqueUrlList);

- Harun Diluka Heshan

Answer 5

Perl，最优化的一行式正则表达式版本：

(?<![^;])([^;]++;)(?=(?>[^;]*;)*?\1)

使用您自己的输入字符串，您自己的正则表达式需要大约114000步才能找到所有匹配项，但使用此正则表达式只需要567步。

在约4秒钟内发现了40000多个匹配项：

实时演示

RegEx 分解：

(?<!    # A Negative lookbehind
    [^;]    # Should be anything other than `;`
)   # End of lookbehind
(   # Capturing group #1
    [^;]++; # Match anything up to first `;`
)   # End of CG #1
(?= # A Positive lookahead
    (?>[^;]*;)*?    # Skip over next path, don't backtrack
    \1  # Until an occurrence
)   # End of lookahead

- revo

---

一种非常好的优化，尽管使用 split 仍然明显更快：https://gist.github.com/haukex/eeebfdaf0951e32be4d0cb5eee3e982d - haukex

你为什么要声称最优化？这是很难证明的。 - Borodin

因为我知道我在说什么？！这消除了大部分的回溯和遇到错误路径后很快失败的情况。 - revo

Answer 6

在Perl中，

#!/usr/bin/env perl

# always use these two
use strict;
use warnings;

my $paths = 'C:\Users\user\Desktop\TESTING\path5;C:\Users\user\Desktop\TESTING\path6;C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path3;';

print "$paths\n";
{
    my %temporary_hash = map { $_ => 1 } split( q{;}, $paths );
    $paths = join( q{;}, keys %temporary_hash );
}
print "$paths\n";

参见perldoc -q duplicate。

- shawnhcorey

Answer 7

在Perl中，使用核心且高度优化的库{{link1：List :: Util }}只需要一行即可完成：

my $newpaths = join ';', uniq split /;/, $paths;

它是如何工作的？split将创建一个路径列表，围绕;字符进行分割；uniq将确保没有重复项；join将再次创建一个以;分隔的路径字符串。

如果路径的大小写不重要，则：

my $newpaths = join ';', uniq split /;/, lc $paths;

完整的程序可能是：

use strict;
use warnings;

use List::Util qw( uniq );

my $paths = 'C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path5;C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path6;C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path3;C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path3;';

my $newpaths = join ';', uniq split /;/, $paths;

print $newpaths, "\n";

为了让事情变得有趣，让我们将此解决方案与使用临时哈希的建议方案进行时间比较。这是计时程序：

use strict;
use warnings;

use List::Util qw( uniq );
use Time::HiRes qw( time );

my @p;
for( my $i = 0; $i < 1000000; $i++ ) {
  push @p, 'C:\This\is\a\random\path' . int(rand(250000));
}
my $paths = join ';', @p;

my $t = time();
my $newpaths = join ';', uniq split /;/, $paths;
$t = time() - $t;
print 'Time with uniq: ', $t, "\n";

$t = time();
my %temp = map { $_ => 1 } split /;/, $paths;
$newpaths = join ';', keys %temp;
$t = time() - $t;
print 'Time with temporaty hash: ', $t, "\n";

它生成了一百万个随机路径，应该有5:1的重复比例（每个路径有5个重复）。我测试过的服务器的时间如下：

Time with uniq: 0.849196910858154
Time with temporaty hash: 1.29486703872681

这使得uniq库比临时哈希更快。带有100:1重复：

Time with uniq: 0.526581048965454
Time with temporaty hash: 0.823433876037598

有10000:1的重复：

Time with uniq: 0.423808097839355
Time with temporaty hash: 0.736939907073975

这两个算法发现重复项越多，它们的工作量就越小。uniq在发现重复项增加时表现更好。

可以随意尝试随机生成器的数字。

- Javier Elices

Answer 8

由于这些是不区分大小写的Windows路径，您可能想要删除除大小写外完全相同的元素

（下一步将是将每个元素通过File :: Spec :: canonpath 推送以查找路径是否相同但表达方式不同，然后可能要考虑链接，但这仅涉及不区分大小写）

我不知道您的请求“使用正则表达式”是否是必需的，但正如您发现的那样，这是一种非常低效的方法

我建议在分号上进行简单的split，并使用{{link1：List :: UtilsBy }}进行不区分大小写的唯一性

use strict;
use warnings 'all';
use feature 'say';

use List::UtilsBy 'uniq_by';

my $p = 'C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path5;C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path6;C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path3;C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path3;';

my $newp = join "", map { "$_;" } uniq_by { lc } split /;/, $p;

say $newp;

输出

C:\Users\user\Desktop\TESTING\path1;C:\Users\user\Desktop\TESTING\path5;C:\Users\user\Desktop\TESTING\path6;C:\Users\user\Desktop\TESTING\path3;

- Borodin