|
I happened accross the Levenshtein algorithm to find the fewest number of changes that can be made to go from one file to another, but I can't figure out how to find the PATH that resulted in that number without taking up O(n*m) memory. Is there some way to find the path WHILE you perform the algorithm? The way I am doing it now is to store the entire n*m array, then find the solution, then traverse the array from end to beginning to find a shortest path. Is there a way, using either another algorithm or by using the modification to Levenshtein where it only takes O(n) memory, where a least-cost change path can be found? Thanks,
Sounds like somebody's got a case of the Mondays
-Jeff
|
|
|
|
|
First you need to define "Binary". Is this a Binary object module with variable length instruction sizes and relative jump offset addressing, or is it a table of numeric data of fixed length?
Dave Augustine
|
|
|
|
|
I have two "files", which I know are made up of some number of bytes. I want to create a difference file that defines the fewest (or near fewest) changes required to convert one "file" into the other. By "file", I mean some finite stream of bytes. I don't know the format, and don't care. All I know is that one "file" was a previous version of the other, so the difference between them should be negligent. However, it could be a bitmap, a word document, a wmv, etc. I did NOT mean two executable files, although after reading your post I see how you came to that conclusion. Any ideas? Thanks,
Sounds like somebody's got a case of the Mondays
-Jeff
|
|
|
|
|
I don't understand the bit about "converting one file into the other". You already have both of the files. I seem to think that you want to keep only one file, and just the difference file to create the other one, just to conserve space. With software, the base is usually kept and differences are collected and then applied in a batch to create the new base. With binary files, however, you probably want to keep the current version and only have the differences to get back the original. This is like the U**X SED for binary, and in reverse.
If this is to be a generic solution for any such archiving, then the solution would probably be different than if it were for one specific file format, or maybe several different solutions depending on the file.
Tell me more about the files.
Dave Augustine.
|
|
|
|
|
Jeff,
I hate to double post, but why don't we move this discussion to another thread of yours because they are so similar. I just responded to your thread about finding maximum substrings. It was at the end of August and the beginning of September last year.
Dave
|
|
|
|
|
Yes, they are similar problems in that I am looking for similarities between two inputs. However, they both require quite different solutions. For example, when finding the longest matching substring, we can stop searching when we cut the potential matches down to the longest current match. Also, the applications are completely different. I was using the longest matching substring algorithm to find matches in strings that were usually smaller than 256 characters. I wrote an algorithm that I thought would be efficient in ONLY finding such a solution. To extend my current solution to find all matching substrings would truely bloat the algorithm, making it very much less efficient than the "dumb" method of doing this. Therefore, the other solution is not usable in this case because I need to find how to modify a string (of bytes) from A to B, and in my case A and B could be very large (say 4 GB) files, so I cannot use an algorithm that requires n^2 memory (such as the levenshtein algorithm that I currently have coded, which takes about 10 minutes for two 15 KB files due to paging the n^2 table in and out of RAM/Cache). However, I CAN afford n^2 time because I am planning on writing this to be a background process to archive old versions of files. These are the reasons why this is a separate post. Thanks in advance for any additional help,
Sounds like somebody's got a case of the Mondays
-Jeff
|
|
|
|
|
Jeff,
Give me a couple of hours to work up the documentation on how to the the MaxStrings function to do a binary file difference. My code is already modified to support this, only the program needs to be changed to read two files instead of only one file for test case string pairs. I may be able to get that done as well. A good test case will be to compare the .EXE files from the first version with the second version.
Dave.
|
|
|
|
|
I have just completed my version to compare two files. I had created a program that just did the MaxSubstring function, and used the source and EXE as the files to compare against with the new file compare version of the files. It compares 161527 bytes to 57897 bytes (161KB to 58KB the source code files) in 1.079 seconds producing a difference file of 13KB. The .EXE comparisons were 41015 bytes to 36916 bytes (41KB to 36KB the .exe files) in .906 seconds producing a 15KB difference file. The algorithm could still stand some tweeking because my debug version (slower but outputs lots of data) shows some sections that consist of many replications of match 1 byte, 1 byte different, match 1 byte... Just addressing each of the differences (file locations and sizes) requires much more file space than the changes themselves. The algorithm is based on my version of the MaxSubstring function. To verify the result, I created another function that took the base file, applied the difference file, reconstructed the second file, and then did a file compare to verify that they were accurate. Are you still interested in the algorithm?
Dave Augustine
|
|
|
|
|
Yeah, I am definitely still interested! I have just been working on this as a side project in my spare time to try and learn a new algorithm/approach. Thanks,
Sounds like somebody's got a case of the Mondays
-Jeff
|
|
|
|
|
The only reason I spent this much time on it was that I thought it was a worthwhile project that I could use myself. Have you got an e-mail I can send the info to?
Dave
|
|
|
|
|
Gullett.16@osu.edu... Thanks again,
Sounds like somebody's got a case of the Mondays
-Jeff
|
|
|
|
|
Jeff,
I do have your E-mail address now. After a complete verification of the process, I uncovered several errors under special conditions, so I had to correct these problems. I have that fixed now, but I then tried to test the algorithm when a file is split across several buffers (file too big for a single buffer) by defining my input buffers smaller than the file sizes I was testing, but ran into several hideous problems with inter-buffer communications. I finally have that working as well. I have a complete, working, tested, solution.
Now, what to send you. I really don't feel comfortable sending the actual code as either an .exe or as an .asm. The implementation is Quick And Dirty, no error checking, assuming everything is correct, etc. I do not want this to ever end up in a commercial environment. Even the explanation is too big to include in a forum post (the algorithm and its explanation probably deserves an article but that would involve a lot of work). Soooo, what do you really need - just the algorithm description so you can implement it in C#?
Dave Augustine.
|
|
|
|
|
Just the description should be fine. Thanks,
Sounds like somebody's got a case of the Mondays
-Jeff
|
|
|
|
|
Jeff,
Description is on the way via E-mail.
Dave Augustine
|
|
|
|
|
Friends,I want to Segment selected region from the video frames, Say from the video frame 1 I selected an actor with no of mouse clicks(to identify the region boundry) manually, I am looking for good and algorithm/Fram Work which can segment it from the bacground or which can set all the pixel except the actor to white in all the rest of the frames
(C++ / C# or any..)
any smart idea pls
Thanx
|
|
|
|
|
I’m posting this question after a conversation with one of my friends.
There are two algorithms that accomplish the same goal – search through XML file. These algorithms are developed by two different academic research groups. A friend of mine works in one of them, and she wants to compare the performance of the algorithms. The problem is that they are implemented in different languages: C++ and Java. Source codes for both are available. The question is – is there an experimental method for comparing the performance of these algorithms without having both of them implemented in the same language? What assumptions are safe to make?
Thanks,
- Nick
|
|
|
|
|
None. Unless the runtimes of the two algorithms are different (say, one is T(n) and the other is T(n*n)), you cannot say which is faster in any language or on any processor with certainty. You will need to either (1) find that the two algorithms have different asymptotic run times, or (2) run benchmarks comparing the two algorithms using different languages, processors, and input data. For the second option, at the end of the day all you can claim is that, "On ___ processor with ___ configuration, and ___ input data, using the ___ compiler (or the ___ runtime engine), the relative runtimes of the two algorithms was ___ and ___". Using this information, you can make certain generalizations with a high level of confidence, but unfortunately asymptotically equivalent algorithms cannot be compared with any level of certainty for all systems, or all compiler optimizations. Good luck,
Sounds like somebody's got a case of the Mondays
-Jeff
|
|
|
|
|
Does anyone know of a good algorithm for calculating minimum whole number ratios.
For instance:
800x600 would be 4x3
300x110 would be 30x11
250x150 would be 5x3
thanks in advance
|
|
|
|
|
Simply divide by the greatest common divisor (gcd)
800x600 gcd(800,600)=200 so you get 4x3 etc
You calculate gcd using Euclid's algorithm, Wikipedia article[^]
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
Hello everyone..
I am planning to design a timetable system for my 3rd year project. I would like to know what is the best algorithm to use for this. will be doing my system in C#, will also have a website using ASP.NET! I want a algorithm that is simple and easy to understand - nothing complex. i'm no einstein. 
|
|
|
|
|
That is a pretty broad post there. What ideas have you come up with?
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
|
|
|
|
|
Its going to be a timetable system that schedules timetables for maybe a university or highschool but right now am looking to base it for the university.. should be able to schedule in the venues - check if venue is big enough for the amount of students in that certain course\module. allocate resources to rooms(resources needed to carry out a lecture) assign lecturers to courses, check for clashes. from whatever information you put into the system - student, lecturer, rooms can have personalised timetable.. dont know if this helps!
someone suggested that i will need to use a scheduling\timetabling algorithm to be able to do this. am not sure.. 
|
|
|
|
|
Angel69 wrote: I am planning to design a timetable system for my 3rd year project. I would like to know what is the best algorithm to use for this.
Algorithm to do what? Work out how to put the timetable together? As I recall some research fellows at my University were attempting to work out the best algorithm when I was there 14 years ago. There results were a disaster. The department used their software and nobody liked the time tables it produced.
|
|
|
|
|
Afaik it might be NP-hard so bad luck there with the simple part.
As in you'll never get optimal result in a polinomial time so very fast your program will have to be running for months to get a full result.
|
|
|
|
|
that would be my concern as well. I have no way to prove it but making that sort of schedule seems reminiscent of the knapsack problem which is NP-Complete.
Otherwise [Microsoft is] toast in the long term no matter how much money they've got. They would be already if the Linux community didn't have it's head so firmly up it's own command line buffer that it looks like taking 15 years to find the desktop.
-- Matthew Faithfull
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
