[perl-python] a program to delete duplicate files

[John Machin]

Re: a program to delete duplicate files


Patrick Useldinger wrote:[color=blue]
> John Machin wrote:
>[color=green]
> > Maybe I was wrong: lawyers are noted for irritating precision. You
> > meant to say in your own defence: "If there are *any* number (n >=[/color][/color]
2)[color=blue][color=green]
> > of identical hashes, you'd still need to *RE*-read and *compare*[/color][/color]
....".[color=blue]
>
> Right, that is what I meant.
>[color=green]
> > 2. As others have explained, with a decent hash function, the
> > probability of a false positive is vanishingly small. Further,[/color][/color]
nobody[color=blue][color=green]
> > in their right mind [1] would contemplate automatically deleting[/color][/color]
n-1[color=blue][color=green]
> > out of a bunch of n reportedly duplicate files without further
> > investigation. Duplicate files are usually (in the same directory[/color][/color]
with[color=blue][color=green]
> > different names or in different-but-related directories with the[/color][/color]
same[color=blue][color=green]
> > names) and/or (have a plausible explanation for how they were
> > duplicated) -- the one-in-zillion-chance false-positive should[/color][/color]
stand[color=blue][color=green]
> > out as implausible.[/color]
>
> Still, if you can get it 100% right automatically, why would you[/color]
bother[color=blue]
> checking manually?[/color]

A human in their right mind is required to decide what to do with the
duplicates. The proponents of hashing -- of which I'm not one -- would
point out that any false-positives would be picked up as part of the
human scrutiny.
[color=blue]
> Why get back to argments like "impossible ",
> "implausibl e", "can't be" if you can have a simple and correct answer[/color]
-[color=blue]
> yes or no?[/color]

Oh yeah, "the computer said so, it must be correct". Even with your
algorithm, I would be investigating cases where files were duplicates
but there was nothing in the names or paths that suggested how that
might have come about.
[color=blue]
>
> Anyway, fdups does not do anything else than report duplicates.
> Deleting, hardlinking or anything else might be an option depending[/color]
on[color=blue]
> the context in which you use fdups, but then we'd have to discuss the[/color]
[color=blue]
> context. I never assumed any context, in order to keep it as[/color]
universal[color=blue]
> as possible.[/color]

That's very good, but it wasn't under contention.
[color=blue]
>[color=green]
> > Different subject: maximum number of files that can be open at[/color][/color]
once. I[color=blue][color=green]
> > raised this issue with you because I had painful memories of having[/color][/color]
to[color=blue][color=green]
> > work around max=20 years ago on MS-DOS and was aware that this[/color][/color]
magic[color=blue][color=green]
> > number was copied blindly from early Unix. I did tell you that
> > empirically I could get 509 successful opens on Win 2000 [add 3 for
> > stdin/out/err to get a plausible number] -- this seems high enough[/color][/color]
to[color=blue][color=green]
> > me compared to the likely number of files with the same size -- but[/color][/color]
you[color=blue][color=green]
> > might like to consider a fall-back detection method instead of just
> > quitting immediately if you ran out of handles.[/color]
>
> For the time being, the additional files will be ignored, and a[/color]
warning[color=blue]
> is issued. fdups does not quit, why are you saying this?[/color]

I beg your pardon, I was wrong. Bad memory. It's the case of running
out of the minuscule buffer pool that you allocate by default where it
panics and pulls the sys.exit(1) rip-cord.
[color=blue]
>
> A fallback solution would be to open the file before every _block_[/color]
read,[color=blue]
> and close it afterwards.[/color]

Ugh. Better use more memory, so less blocks!!
[color=blue]
> In my mind, it would be a command-line option,
> because it's difficult to determine the number of available file[/color]
handles[color=blue]
> in a multitasking environment.[/color]

The pythonic way is to press ahead optimistically and recover if you
get bad news.
[color=blue]
>
> Not difficult to implement, but I first wanted to refactor the code[/color]
so[color=blue]
> that it's a proper class that can be used in other Python programs,[/color]
as[color=blue]
> you also asked.[/color]

I didn't "ask"; I suggested. I would never suggest a
class-for-classes-sake. You had already a singleton class; why
another". What I did suggest was that you provide a callable interface
that returned clusters of duplicates [so that people could do their own
thing instead of having to parse your file output which contains a
mixture of warning & info messages and data].
[color=blue]
> That is what I have sent you tonight. It's not that I
> don't care about the file handle problem, it's just that I do changes[/color]
by[color=blue]
> (my own) priority.
>[color=green]
> > You wrote at some stage in this thread that (a) this caused[/color][/color]
problems on[color=blue][color=green]
> > Windows and (b) you hadn't had any such problems on Linux.
> >
> > Re (a): what evidence do you have?[/color]
>
> I've had the case myself on my girlfriend's XP box. It was certainly
> less than 500 files of the same length.[/color]

Interesting. Less on XP than on 2000? Maybe there's a machine-wide
limit, not a per-process limit, like the old DOS max=20. What else was
running at the time?
[color=blue]
>[color=green]
> > Re (b): famous last words! How long would it take you to do a test[/color][/color]
and[color=blue][color=green]
> > announce the margin of safety that you have?[/color]
>
> Sorry, I do not understand what you mean by this.[/color]

Test:
!for k in range(1000):
! open('foo' + str(k), 'w')
Announce:
"I can open A files at once on box B running os C. The most files of
the same length that I have seen is D. The ratio A/D is small enough
not to worry."

Cheers,
John

[Patrick Useldinger]

Re: a program to delete duplicate files

John Machin wrote:
[color=blue]
> Oh yeah, "the computer said so, it must be correct". Even with your
> algorithm, I would be investigating cases where files were duplicates
> but there was nothing in the names or paths that suggested how that
> might have come about.[/color]

Of course, but it's good to know that the computer is right, isn't it?
That leaves the human to take decisions instead of double-checking.
[color=blue]
> I beg your pardon, I was wrong. Bad memory. It's the case of running
> out of the minuscule buffer pool that you allocate by default where it
> panics and pulls the sys.exit(1) rip-cord.[/color]

Bufferpool is a parameter, and the default values allow for 4096 files
of the same size. It's more likely to run out of file handles than out
of bufferspace, don't you think?
[color=blue]
> The pythonic way is to press ahead optimistically and recover if you
> get bad news.[/color]

You're right, that's what I thought about afterwards. Current idea is to
design a second class that opens/closes/reads the files and handles the
situation independantly of the main class.
[color=blue]
> I didn't "ask"; I suggested. I would never suggest a
> class-for-classes-sake. You had already a singleton class; why
> another". What I did suggest was that you provide a callable interface
> that returned clusters of duplicates [so that people could do their own
> thing instead of having to parse your file output which contains a
> mixture of warning & info messages and data].[/color]

That is what I have submitted to you. Are you sure that *I* am the
lawyer here?
[color=blue][color=green][color=darkred]
>>>Re (a): what evidence do you have?[/color][/color][/color]

See ;-)
[color=blue]
> Interesting. Less on XP than on 2000? Maybe there's a machine-wide
> limit, not a per-process limit, like the old DOS max=20. What else was
> running at the time?[/color]

Nothing I started manually, but the usual bunch of local firewall, virus
scanner (not doing a complete machine check at that time).
[color=blue]
> Test:
> !for k in range(1000):
> ! open('foo' + str(k), 'w')[/color]

I'll try that.
[color=blue]
> Announce:
> "I can open A files at once on box B running os C. The most files of
> the same length that I have seen is D. The ratio A/D is small enough
> not to worry."[/color]

I wouldn't count on that on a multi-tasking environment, as I said. The
class I described earlier seems a cleaner approach.

Regards,
-pu

[Patrick Useldinger]

Re: a program to delete duplicate files

John Machin wrote:
[color=blue]
> Test:
> !for k in range(1000):
> ! open('foo' + str(k), 'w')[/color]

I ran that and watched it open 2 million files and going strong ...
until I figured that files are closed by Python immediately because
there's no reference to them ;-)

Here's my code:

#!/usr/bin/env python
import os
print 'max number of file handles today is',
n = 0
h = []
try:
while True:
filename = 'mfh' + str(n)
h.append((file( filename,'w'),f ilename))
n = n + 1
except:
print n
for handle, filename in h:
handle.close()
os.remove(filen ame)

On Slackware 10.1, this yields 1021.
On WinXPSP2, this yields 509.

-pu

[David Eppstein]

Re: a program to delete duplicate files

In article <1110617519.413 704.237830@g14g 2000cwa.googleg roups.com>,
"John Machin" <sjmachin@lexic on.net> wrote:
[color=blue]
> Just look at the efficiency of processing N files of the same size S,
> where they differ after d bytes: [If they don't differ, d = S][/color]

I think this misses the point. It's easy to find the files that are
different. Just a file size comparison will get most of them, and most
of the rest can be detected in the first few kbytes. So I think it's
safe to assume both of these filtering mechanisms would be incorporated
into a good duplicate detection code, and that any remaining tests that
would be performed are between files that are very likely to be the same
as each other.

The hard part is verifying that the files that look like duplicates
really are duplicates. To do so, for a group of m files that appear to
be the same, requires 2(m-1) reads through the whole files if you use a
comparison based method, or m reads if you use a strong hashing method.
You can't hope to cut the reads off early when using comparisons,
because the files won't be different.

The question to me is: when you have a group of m>2 likely-to-be-equal
files, is 2(m-1) reads and very little computation better than m reads
and a strong hash computation? I haven't yet seen an answer to this,
but it's a question for experimentation rather than theory.

--
David Eppstein
Computer Science Dept., Univ. of California, Irvine
http://www.ics.uci.edu/~eppstein/

[David Eppstein]

Re: a program to delete duplicate files

In article <4232da24$1@new s.vo.lu>,
Patrick Useldinger <pu.news.001@gm ail.com> wrote:
[color=blue]
> Shouldn't you add the additional comparison time that has to be done
> after hash calculation? Hashes do not give 100% guarantee.[/color]

When I've been talking about hashes, I've been assuming very strong
cryptographic hashes, good enough that you can trust equal results to
really be equal without having to verify by a comparison.

--
David Eppstein
Computer Science Dept., Univ. of California, Irvine
http://www.ics.uci.edu/~eppstein/

[Patrick Useldinger]

Re: a program to delete duplicate files

David Eppstein wrote:
[color=blue]
> When I've been talking about hashes, I've been assuming very strong
> cryptographic hashes, good enough that you can trust equal results to
> really be equal without having to verify by a comparison.[/color]

I am not an expert in this field. All I know is that MD5 and SHA1 can
create collisions. Are there stronger algorithms that do not? And, more
importantly, has it been *proved* that they do not?

-pu

[Patrick Useldinger]

Re: a program to delete duplicate files

David Eppstein wrote:
[color=blue]
> The hard part is verifying that the files that look like duplicates
> really are duplicates. To do so, for a group of m files that appear to
> be the same, requires 2(m-1) reads through the whole files if you use a
> comparison based method, or m reads if you use a strong hashing method.
> You can't hope to cut the reads off early when using comparisons,
> because the files won't be different.[/color]

If you read them in parallel, it's _at most_ m (m is the worst case
here), not 2(m-1). In my tests, it has always significantly less than m.

-pu

[Bengt Richter]

Re: a program to delete duplicate files

On Mon, 14 Mar 2005 10:43:23 -0800, David Eppstein <eppstein@ics.u ci.edu> wrote:
[color=blue]
>In article <1110617519.413 704.237830@g14g 2000cwa.googleg roups.com>,
> "John Machin" <sjmachin@lexic on.net> wrote:
>[color=green]
>> Just look at the efficiency of processing N files of the same size S,
>> where they differ after d bytes: [If they don't differ, d = S][/color]
>
>I think this misses the point. It's easy to find the files that are
>different. Just a file size comparison will get most of them, and most
>of the rest can be detected in the first few kbytes. So I think it's
>safe to assume both of these filtering mechanisms would be incorporated
>into a good duplicate detection code, and that any remaining tests that
>would be performed are between files that are very likely to be the same
>as each other.
>
>The hard part is verifying that the files that look like duplicates
>really are duplicates. To do so, for a group of m files that appear to
>be the same, requires 2(m-1) reads through the whole files if you use a
>comparison based method, or m reads if you use a strong hashing method.[/color]
What do you mean by "a comparison based method" ? Are you excluding the
possibility of parallel reading and comparing? The problem then becomes
verifying that m buffers containing corresponding segments of the files
are equal. You could do that by comparing hashes of the buffers (or updated
running hashes for the whole files so far read), or you could compare the
buffers in parallel byte by byte if that turns out efficient to implement
in the given language and os environment. Small buffers would probably
not be efficient for disk access, but too large might not be good either.
Maybe some automatic tuning algorithm could be developed to optimize
comparison operations in the shadow of i/o. But does the OS accept hints
about read-ahead buffering? Are the disks SCSI raid or USB external or
networked? Can automatic tuning achieve an optimum disregarding all that?

What is it that we're trying to optimize? Time to classify the
whole file set into groups of equivalent files? (note that there can be
multiple groups that are internally equal but uneqal to members of other groups).

The problem of limitation on the number of simultaneously open files could
be virtualized away, and only have impact when the limit is actually encountered.
[color=blue]
>You can't hope to cut the reads off early when using comparisons,
>because the files won't be different.[/color]
So the worst case will be reading all through to the end once in parallel.
But pre-hashing guarantees the worst case for all -- unless disk access patterns
happen to make that the most efficient way to get everything read and compared
when most are equal.[color=blue]
>
>The question to me is: when you have a group of m>2 likely-to-be-equal
>files, is 2(m-1) reads and very little computation better than m reads
>and a strong hash computation? I haven't yet seen an answer to this,
>but it's a question for experimentation rather than theory.[/color]
ISTM 2(m-1) reads is not necessary, so "the question" to me doesn't involve that ;-)

Regards,
Bengt Richter

[John J. Lee]

Re: a program to delete duplicate files

Patrick Useldinger <pu.news.001@gm ail.com> writes:[color=blue]
> John Machin wrote:[/color]
[...][color=blue][color=green]
> > 2. As others have explained, with a decent hash function, the
> > probability of a false positive is vanishingly small. Further, nobody[/color][/color]
[...][color=blue]
> Still, if you can get it 100% right automatically, why would you
> bother checking manually? Why get back to argments like "impossible ",
> "implausibl e", "can't be" if you can have a simple and correct answer
> -
> yes or no?[/color]
[...]

Well, as Francois pointed out, it is strictly not physically possible
to obtain a perfectly reliable answer, even if you *do* do the
comparison.

Even so, you're right on this point (though IIUC it's not practically
important ATM): regardless of wild flukes, people can deliberately
wangle files to get a hash collision. so comparison is better than
hashing from this PoV.


John

[John J. Lee]

Re: a program to delete duplicate files

Patrick Useldinger <pu.news.001@gm ail.com> writes:
[color=blue]
> David Eppstein wrote:
>[color=green]
> > The hard part is verifying that the files that look like duplicates
> > really are duplicates. To do so, for a group of m files that appear
> > to be the same, requires 2(m-1) reads through the whole files if you
> > use a comparison based method, or m reads if you use a strong
> > hashing method. You can't hope to cut the reads off early when
> > using comparisons, because the files won't be different.[/color]
>
> If you read them in parallel, it's _at most_ m (m is the worst case
> here), not 2(m-1). In my tests, it has always significantly less than
> m.[/color]

Hmm, Patrick's right, David, isn't he?

Except when m gets really BIG (say, M), in which case I suppose m is
no longer the worst case number of whole-file reads.

And I'm not sure what the trade off between disk seeks and disk reads
does to the problem, in practice (with caching and realistic memory
constraints).


John

[Jeff Shannon]

Re: a program to delete duplicate files

Patrick Useldinger wrote:
[color=blue]
> David Eppstein wrote:
>[color=green]
>> When I've been talking about hashes, I've been assuming very strong
>> cryptographic hashes, good enough that you can trust equal results to
>> really be equal without having to verify by a comparison.[/color]
>
> I am not an expert in this field. All I know is that MD5 and SHA1 can
> create collisions. Are there stronger algorithms that do not? And, more
> importantly, has it been *proved* that they do not?[/color]

I'm not an expert either, but I seem to remember reading recently
that, while it's been proven that it's possible for SHA1 to have
collisions, no actual collisions have been found. Even if that's not
completely correct, you're *far* more likely to be killed by a
meteorite than to stumble across a SHA1 collision. Heck, I'd expect
that it's more likely for civilization to be destroyed by a
dinosaur-killer-sized meteor.

With very few exceptions, if you're contorting yourself to avoid SHA1
hash collisions, then you should also be wearing meteor-proof (and
lightning-proof) armor everywhere you go. (Those few exceptions would
be cases where a malicious attacker stands to gain enough from
constructing a single hash collision to make it worthwhile to invest a
*large* number of petaflops of processing power.) Sure it's not "100%
perfect", but... how perfect do you *really* need?

Jeff Shannon

[David Eppstein]

Re: a program to delete duplicate files

In article <871xaisdqz.fsf @pobox.com>, jjl@pobox.com (John J. Lee)
wrote:
[color=blue][color=green]
> > If you read them in parallel, it's _at most_ m (m is the worst case
> > here), not 2(m-1). In my tests, it has always significantly less than
> > m.[/color]
>
> Hmm, Patrick's right, David, isn't he?[/color]

Yes, I was only considering pairwise comparisons. As he says,
simultaneously comparing all files in a group would avoid repeated reads
without the CPU overhead of a strong hash. Assuming you use a system
that allows you to have enough files open at once...
[color=blue]
> And I'm not sure what the trade off between disk seeks and disk reads
> does to the problem, in practice (with caching and realistic memory
> constraints).[/color]

Another interesting point.

--
David Eppstein
Computer Science Dept., Univ. of California, Irvine
http://www.ics.uci.edu/~eppstein/

[Claudio Grondi]

Re: [perl-python] a program to delete duplicate files

>> I'll post my version in a few days.
Have I missed something?
Where can I see your version?

Claudio


"Xah Lee" <xah@xahlee.org > schrieb im Newsbeitrag
news:1110372973 .657649.212920@ l41g2000cwc.goo glegroups.com.. .[color=blue]
> here's a large exercise that uses what we built before.
>
> suppose you have tens of thousands of files in various directories.
> Some of these files are identical, but you don't know which ones are
> identical with which. Write a program that prints out which file are
> redundant copies.
>
> Here's the spec.
> --------------------------
> The program is to be used on the command line. Its arguments are one or
> more full paths of directories.
>
> perl del_dup.pl dir1
>
> prints the full paths of all files in dir1 that are duplicate.
> (including files in sub-directories) More specifically, if file A has
> duplicates, A's full path will be printed on a line, immediately
> followed the full paths of all other files that is a copy of A. These
> duplicates's full paths will be prefixed with "rm " string. A empty
> line follows a group of duplicates.
>
> Here's a sample output.
>
> inPath/a.jpg
> rm inPath/b.jpg
> rm inPath/3/a.jpg
> rm inPath/hh/eu.jpg
>
> inPath/ou.jpg
> rm inPath/23/a.jpg
> rm inPath/hh33/eu.jpg
>
> order does not matter. (i.e. which file will not be "rm " does not
> matter.)
>
> ------------------------
>
> perl del_dup.pl dir1 dir2
>
> will do the same as above, except that duplicates within dir1 or dir2
> themselves not considered. That is, all files in dir1 are compared to
> all files in dir2. (including subdirectories) And, only files in dir2
> will have the "rm " prefix.
>
> One way to understand this is to imagine lots of image files in both
> dir. One is certain that there are no duplicates within each dir
> themselves. (imagine that del_dup.pl has run on each already) Files in
> dir1 has already been categorized into sub directories by human. So
> that when there are duplicates among dir1 and dir2, one wants the
> version in dir2 to be deleted, leaving the organization in dir1 intact.
>
> perl del_dup.pl dir1 dir2 dir3 ...
>
> does the same as above, except files in later dir will have "rm "
> first. So, if there are these identical files:
>
> dir2/a
> dir2/b
> dir4/c
> dir4/d
>
> the c and d will both have "rm " prefix for sure. (which one has "rm "
> in dir2 does not matter) Note, although dir2 doesn't compare files
> inside itself, but duplicates still may be implicitly found by indirect
> comparison. i.e. a==c, b==c, therefore a==b, even though a and b are
> never compared.
>
>
> --------------------------
>
> Write a Perl or Python version of the program.
>
> a absolute requirement in this problem is to minimize the number of
> comparison made between files. This is a part of the spec.
>
> feel free to write it however you want. I'll post my version in a few
> days.
>
> http://www.xahlee.org/perl-python/python.html
>
> Xah
> xah@xahlee.org
> http://xahlee.org/PageTwo_dir/more.html
>[/color]

[Xah Lee]

Re:[perl-python] a program to delete duplicate files

Sorry i've been busy...

Here's the Perl code. I have yet to clean up the code and make it
compatible with the cleaned spec above. The code as it is performs the
same algorithm as the spec, just doesn't print the output as such. In a
few days, i'll post a clean version, and also a Python version, as well
a sample directory for testing purposes. (The Perl code has gone thru
many testings and is considered correct.)

The Perl code comes in 3 files as it is:

Combo114.pm
Genpair114.pm
del_dup.pl

The main program is del_dup.pl. Run it on the command line as by the
spec. If you want to actually delete the dup files, uncomment the
"unlink" line at the bottom. Note: the module names don't have any
significance.


Note: here's also these python files ready to go for the final python
version. Possibly the final propram should be just a single file...

Combo114.py
Genpair114.py


Here're the files: del_dup.zip
-----
to get the code and full detail with latest update, please see:

http://xahlee.org/perl-python/delete_dup_files.html

Xah
xah@xahlee.org

http://xahlee.org/PageTwo_dir/more.html

Claudio Grondi wrote:[color=blue][color=green][color=darkred]
> >> I'll post my version in a few days.[/color][/color]
> Have I missed something?
> Where can I see your version?
>
> Claudio[/color]

[alanwo@gmail.com]

Re: a program to delete duplicate files

Why not try to use NoClone, it finds and deletes duplicate files by
true byte-by-byte comparison. Smart marker filters duplicate files to
delete. With GUI.

http://noclone.net

Xah Lee wrote:[color=blue]
> here's a large exercise that uses what we built before.
>
> suppose you have tens of thousands of files in various directories.
> Some of these files are identical, but you don't know which ones are
> identical with which. Write a program that prints out which file are
> redundant copies.
>
> Here's the spec.
> --------------------------
> The program is to be used on the command line. Its arguments are one[/color]
or[color=blue]
> more full paths of directories.
>
> perl del_dup.pl dir1
>
> prints the full paths of all files in dir1 that are duplicate.
> (including files in sub-directories) More specifically, if file A has
> duplicates, A's full path will be printed on a line, immediately
> followed the full paths of all other files that is a copy of A. These
> duplicates's full paths will be prefixed with "rm " string. A empty
> line follows a group of duplicates.
>
> Here's a sample output.
>
> inPath/a.jpg
> rm inPath/b.jpg
> rm inPath/3/a.jpg
> rm inPath/hh/eu.jpg
>
> inPath/ou.jpg
> rm inPath/23/a.jpg
> rm inPath/hh33/eu.jpg
>
> order does not matter. (i.e. which file will not be "rm " does not
> matter.)
>
> ------------------------
>
> perl del_dup.pl dir1 dir2
>
> will do the same as above, except that duplicates within dir1 or dir2
> themselves not considered. That is, all files in dir1 are compared to
> all files in dir2. (including subdirectories) And, only files in dir2
> will have the "rm " prefix.
>
> One way to understand this is to imagine lots of image files in both
> dir. One is certain that there are no duplicates within each dir
> themselves. (imagine that del_dup.pl has run on each already) Files[/color]
in[color=blue]
> dir1 has already been categorized into sub directories by human. So
> that when there are duplicates among dir1 and dir2, one wants the
> version in dir2 to be deleted, leaving the organization in dir1[/color]
intact.[color=blue]
>
> perl del_dup.pl dir1 dir2 dir3 ...
>
> does the same as above, except files in later dir will have "rm "
> first. So, if there are these identical files:
>
> dir2/a
> dir2/b
> dir4/c
> dir4/d
>
> the c and d will both have "rm " prefix for sure. (which one has "rm[/color]
"[color=blue]
> in dir2 does not matter) Note, although dir2 doesn't compare files
> inside itself, but duplicates still may be implicitly found by[/color]
indirect[color=blue]
> comparison. i.e. a==c, b==c, therefore a==b, even though a and b are
> never compared.
>
>
> --------------------------
>
> Write a Perl or Python version of the program.
>
> a absolute requirement in this problem is to minimize the number of
> comparison made between files. This is a part of the spec.
>
> feel free to write it however you want. I'll post my version in a few
> days.
>
> http://www.xahlee.org/perl-python/python.html
>
> Xah
> xah@xahlee.org
> http://xahlee.org/PageTwo_dir/more.html[/color]