Wikipedia:Reference desk/Archives/Computing/2013 December 12

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 12

MP3 file compression.

Why when I 7zip an MP3 file of just 158KB it goes up in file size to 162KB?

Tech info, Intro to Info Tech. Thanks. David Smith. 12/12/2013. 14:09 Thesmithster (talk) 03:10, 12 December 2013 (UTC)

My guess, it was unable to compress the file any further, but added some overhead to describe the new compression method. StuRat (talk) 03:22, 12 December 2013 (UTC)

It is a mathematical certainty that no lossless file compression algorithm can EVER absolutely guarantee to shrink every possible file - every single one of them will actually slightly increase the size of worst-case files....which is what's happening to you here. Typically, files that have already been compressed (as an MP3 certainly has) have already had most of the waste squeezed out of them - and it's fairly unlikely that more remains to be removed.

Think about it like this: If I had a program that could compress every single file you gave it - then you could take the output of the program and compress it some more by running it through the same program again! Keep doing this and eventually, you'd be able to store an infinite amount of "stuff" in just one bit! Clearly that's not possible.

That said, "LOSSY" compression can indeed guarantee that files get smaller - but they also get more and more screwed up. SteveBaker (talk) 21:54, 12 December 2013 (UTC)

There is always overhead, but I'm surprised it's so large. Deflate, the most common compression method in .zip files, has less than 0.01% overhead on already-compressed data. LZMA, the most common compression method in .7z files, usually compresses better than deflate, but seems to have over 1% overhead on already-compressed data. You could save some space by telling 7-Zip to use deflate on these files (you can still use the .7z format—it supports deflate). -- BenRG (talk) 21:07, 13 December 2013 (UTC)

I wouldn't expect the overhead to be strictly multiplicative. I'd expect at least a portion of it to be purely additive. Therefore, in the case of fairly small files, like this one, even a small amount of added data is fairly large percentage of the total size. StuRat (talk) 06:22, 14 December 2013 (UTC)

I agree. You'd kinda hope that there would be a small header in the "compressed" file that contained the compression technique used. It would really be worth having a "Didn't compress the file at all" flag in there - which would limit the amount of expansion for incompressible files to a couple of bytes and probably not increase the size of compressed files at all. Is it possible you used some option to force the compression tool to use a specific algorithm? eg, if you force it to use the "DEFLATE" algorithm, it'll make already-compressed files MUCH bigger than if you let the tool figure out the best algorithm by itself. SteveBaker (talk) 01:33, 15 December 2013 (UTC)

Some sort of big apple ....

• http://bits.blogs.nytimes.com/2013/11/20/a-gift-from-steve-jobs-returns-home/

He gave the organization the computer around 1980, to help Seva enter and analyze survey data from its eye surgeries in Nepal.

“You’ll never be able to use all the memory,” Dr. Brilliant recalled Mr. Jobs telling him. “It’s five megabytes!’”

How could a 1980 Apple ][ have five megabytes memory? -- Toytoy (talk) 12:09, 12 December 2013 (UTC)

Apple ProFile -- Finlay McWalterჷTalk 12:25, 12 December 2013 (UTC)

The quote ambiguously uses the term "memory" to refer to the hard disk drive. This may be a quoted error by the journalist, or by the doctor; or it may be an accurate verbatim statement. Today, we commonly mean "RAM" when we use the term "memory" - but that has not always been true, and may not always be true in the future either. Five megabyte hard disk drives were certainly possible: history of hard disk drives. In the early 1980s, that was a large size for a personal computer, but commercial mainframes commonly had much larger hard disk drives. Nimur (talk) 12:38, 12 December 2013 (UTC)

I'm suspicious of the quote regardless. Five megabytes wasn't much even back then—Apple Disk II floppies held 140K, and I bet a lot of people had more than 35 of them. -- BenRG (talk) 21:14, 13 December 2013 (UTC)

Neither my HP laptop nor Olympus digital camera can read the thousands of images in my SD card anymore. Help me see them again, please?

After I inserted the 32 GB SD card into my computer (Windows 7 Ultimate, 64-bit), I tried to create new folders so I can sort my photos and videos more easily.

It wouldn't allow me to create a new folder ("error 65535") so I created new folders in my main C: drive and tried to copy them into my SD card. There was another error, then I get a prompt saying something about my SD card not being formatted, and whether to format my SD card. I knew that formatting would erase the thousands of media I've snapped or recorded since 2012, so I had to click "no."

I took out and re-inserted my SD card. The computer registered an SD card being in there, but it asked me to format the card again!

Then I put the card back into the camera to see if it would still recognize my files. As soon as I turned the camera on, it would prompt the two "CARD SETUP" menu options: "Power Off" and "Format."

I could not believe my eyes! This would be a HORRIBLE thing to happen to me.

Please help me see my files again, please, so I can at least get them backed up. Thanks! --Let Us Update Wikipedia: Dusty Articles 16:27, 12 December 2013 (UTC)

I'm not sure what has happened, but you might take a look at http://www.wiki-errors.com/err.php?wiki=65535. Looie496 (talk) 16:39, 12 December 2013 (UTC)

That site looks extremely suspicious. All of the pages contain the exact same text just with the supposed error code replaced by whatever you searched for. For example putting "err.php?wiki=WIKIPEDIA_REF_DESK" as the url brings up a page that talks about the "WIKIPEDIA_REF_DESK" file system error and offers a download to fix the "error" (most likely a virus). 82.44.76.14 (talk) 20:08, 12 December 2013 (UTC)

This www.wiki-errors.com is absolutely, definitely, beyond any shadow of a doubt, a 100% pure scam site, with no intention other than tricking you to downloading malware. Reasons:

1. As 82.44.76.14 above said, it will present the same page regardless of what was written after the ?wiki= parameter.
2. It is a "wiki" in appearance only. There is no option to edit pages or view the history, not even to sign up for an account.
3. If you look at the contents, you see many sections about common computing areas. The same pages are repeated within multiple sections, with no regard to what page belongs to what section.
4. Pretty much every page suggest you to download a Windows EXE file as a "magic bullet" to fix errors. This EXE file is, without any shadow of a doubt, malware.
5. The contacts page contains an address in the UK. The site itself is registered in the USA.
6. Numerous on-line website credibility sites claim this site is not at all credible or thrustworthy.

In conclusion, please avoid this site at all costs. JIP | Talk 21:02, 13 December 2013 (UTC)

Yes, you are so correct! I have a Chrome plugin named WOT (Web of Trust) that gives different colors of rings next to website URLs. Green means it's a good, trustworthy site (Wikipedia's ring is green) and red means it's a site to be avoided because mal-intent is known to be there. Yellow or gold means someplace in between; either the site is slightly unsafe or the raters are on their way to making it red as the site becomes more known. A silver or gray ring with a question mark means it's not known well enough by the WOT users to have a rating. The ring for that Wiki Errors site is yellowish-gold, and its reports are none too flattering. Anyone interested in protecting their surfing experience must use Web of Trust. --Let Us Update Wikipedia: Dusty Articles 01:23, 14 December 2013 (UTC)

Sadly, it sounds like you may need the services of a Data Recovery professional. They're not cheap. (BTW, They're more likely to be successful the less you mess with the card.) APL (talk) 17:03, 12 December 2013 (UTC)

I agree that you should not write anything to the card, and certainly don't format it (though a low level format would probably not delete the pictures). There may be no need to pay anyone to recover images from the card, because there are various free programmes that will attempt this for you. I've been using "PC Inspector: Smart Recovery" by CONVAR for many years, and it has seldom failed to recover lost pictures. Here's the CNET download. It's not particularly user-friendly, and it's extremely slow, but it works! I've had it find pictures that I deleted years ago! Ask here if you need guidance on using it. Dbfirs 17:11, 12 December 2013 (UTC)

Before LUUWDA tries that, mightn't it be better to make an image of the entire card? LUUWDA, it sounds like you're a Windows user; I don't know if you have access to a Linux system, but if you know someone who does, you might have him/her use the dd command to copy the whole thing including partition table (that is, something like dd if=/dev/sdc ... rather than dd if=/dev/sdc1 ...; the latter would attempt to copy a partition but not the partition table). Make sure the partition is not mounted when you try it. Then you could play all sorts of games on the image, without worrying about doing further damage to the data on the card. --Trovatore (talk) 20:19, 12 December 2013 (UTC)

I don't use Linux, but does that command copy sectors independently of the file table? (If so, then it would certainly be useful, and I'd like to try it myself.) The only problem would be that if the file table is corrupt, then special software would still be needed to recreate a file for each picture. Dbfirs 23:34, 12 December 2013 (UTC)

It should do that, yes, though of course I don't guarantee anything and you're on your own if it goes wrong. Honestly I'm not sure you couldn't do the same thing with cp, copying from /dev/sdc (or wherever the block device shows up), but for some reason instructions for this sort of low-level copying almost always specify dd. Can anyone explain why? --Trovatore (talk) 01:19, 13 December 2013 (UTC)

Well cp seems to copy at file level, so that wouldn't be any use if Linux couldn't see any files on the flash drive. If dd copies at sector level, then that sounds useful, though I don't advise using it without the write-protect notch engaged on the flash drive. It would be all too easy for the novice user to overwrite pictures with data from elsewhere. The software that I linked reads sector by sector and tries to build picture files (jpg etc). It then writes any rebuilt files to another drive. Dbfirs 13:50, 13 December 2013 (UTC)

From the Linux point of view, /dev/sdc is a file (see everything is a file), so that's not the problem. Running cp from /dev/sdc should still be trying to copy the card, not the files in a filesystem on the card. I think the problem is that it wouldn't know where to stop. With dd, you can specify the exact amount of data you want. --Trovatore (talk) 17:20, 13 December 2013 (UTC)

Yes, I see what you mean. As long as Linux has access to individual sectors, dd or cp should be able to read on and on to the end of the card, though the data would probably be all mixed up. Something like ddrescue would presumably attempt to put it back together. It's thirty years since I used to recover files from damaged floppy discs by hand (reading whole tracks into a text editor and extracting sectors), and I've never used any Windows software to read tracks or sectors. Doesn't Windows get confused if it can't find sector headers? I must learn to use Linux! Dbfirs 17:51, 13 December 2013 (UTC)

/dev/sdc is a special type of file called a "device node": it's a filesystem object that refers to a piece of hardware. "cp" works at the filesystem level, and using it to copy the file will just give you another device node that refers to the same hardware. "dd", on the other hand, works at the block level, and when used on a block device such as /dev/sdc, will copy the data stored on the device. --Carnildo (talk) 04:12, 14 December 2013 (UTC)

Thanks, that makes sense. What about cat /dev/sdc? --Trovatore (talk) 09:28, 15 December 2013 (UTC)

Just another thought. I wonder if you accidentally tried to write to the card from your computer. Sometimes this is successful, but I've had so much trouble when trying to write to a camera-formatted card (getting symptoms very similar to yours but without the 65535 error), that I now adopt the policy: Never write to a camera-formatted card; always copy pictures to the hard drive before editing them. Dbfirs 17:29, 12 December 2013 (UTC)

Yes, User:Dbfirs, of a sort. I tried to create a new folder to that card; wouldn't work, so I thought I'd circumvent that by creating a new folder from the C: drive and then moving it onto the card. That's when this problem started. --Let Us Update Wikipedia: Dusty Articles 15:18, 13 December 2013 (UTC)

I can't explain why that causes problems. Possibly the camera uses a special file system, but I've had similar problems when writing to a camera card. Sometimes it works OK and sometimes it seems to trash the file table on the card. Sometime I might try Trovatore's Linux command to see what has happened to the file system, but its many years since I played around with file systems and reading individual sectors. Have you tried any recovery software? I'd recommend making the card read only with the little switch, whatever you try, until you get your pictures back. If you are into Linux, you might try Trovatore's suggestion via ddrescue, but I find the Convar software adequate for most card faults. Dbfirs 17:22, 13 December 2013 (UTC)

By the way, you should be aware that the little switch doesn't actually prevent writing to the card. It tells the gadget the card is attached to that it's not supposed to write to the card, but it's up to the gadget. Some card readers may honor the request at the hardware level, but for other devices, the decision is made at the firmware or software level.

For example, if you make your card bootable and install CHDK in the boot sector, then to actually get CHDK to run on your compatible Canon camera, you actually have to set the switch to the read-only position. The CHDK then loads itself into the volatile copy of the firmware on your camera (the non-volatile firmware is not actually flashed) — and then goes about ignoring the switch, except as a signal that CHDK should run rather than deferring to the camera firmware. Otherwise you wouldn't be able to take pictures. --Trovatore (talk) 01:24, 14 December 2013 (UTC)

Thanks for the warning and the interesting link. Dbfirs 07:50, 14 December 2013 (UTC)

65535 = binary 1111111111111111 = -1 in sixteen bits, so really this is just "error -1" and might not mean anything beyond "error".  Card Zero  (talk) 20:38, 12 December 2013 (UTC)

That PC Inspector: Smart Recovery certainly can work, and it does not modify the card, but needs space on your hard drive to put the recovered images. Also for 32GB it could easily take more than a day to recover. Graeme Bartlett (talk) 22:57, 13 December 2013 (UTC)

That sounds just about right. I started the CONVAR PC Inspector: Smart Recovery sometime between 10-11 in the morning, and as of 7:22 PM (CST), it is only 45% done! At least I am seeing my files again already though, so very well worth the wait! I couldn't believe so many other card recovery software would offer to scan and find my lost files for free, but try to CHARGE me (ranged from $25-$70!) to actually perform the recoveries! --Let Us Update Wikipedia: Dusty Articles 01:23, 14 December 2013 (UTC)

It will possibly recover lots of files that you deleted long ago, but it would be wise to let it continue in case there are some files that you want near the "end" of the card. (New files can be written anywhere on the card if wear levelling is implemented.) Dbfirs 07:50, 14 December 2013 (UTC)

Identifying best Big-O

hello, i got another question. i was given this multiple choice question on a test:

Identify the best Big-O when inserting a new element as the largest item in an ordered collection. The three collections are: ArrayList, LinkedList and TreeSet. Assume that you already know its target location and the fastest possible algorithm for the given collection constraints.

	ArrayList	LinkedList	TreeSet
a)	O(n)	O(1)	O(1)
b)	O(logn)	O(n)	O(logn)
c)	O(1)	O(n)	O(logn)
d)	O(1)	O(1)	O(logn)
e)	none of the above

d) was the correct answer, but i dont understand why. What about a), where TreeSet and LinkedList are O(1)? And here was another similar question:

Identify the best Big-O when inserting a new element as the smallest item in an ordered collection. The three collections are: ArrayList, LinkedList and TreeSet. Assume the fastest possible algorithm for the given collection constraints.

	ArrayList	LinkedList	TreeSet
a)	O(n)	O(1)	O(1)
b)	O(logn)	O(n)	O(logn)
c)	O(1)	O(n)	O(logn)
d)	O(1)	O(1)	O(logn)
e)	none of the above

The answer was e), none of the above, with the big-O's being O(n) for ArrayList, O(1) for LinkedList, and O(logn) for TreeSet. Where do these answers come from? Do I just have to memorize big-O's?Sdjkgkdjfag999 (talk) 17:09, 12 December 2013 (UTC)

You either have to memorize them - or understand how the underlying algorithms actually work and figure it out from there. If you're discussing this as a programmer, then you should certainly understand how each algorithm works and from there you can easily understand which O value is the appropriate one. One word of caution - it's dangerous to assume that (say) an O(logn) algorithm is faster than (say) an O(n) algorithm because sometimes the complexity of one "step" of the O(logn) approach may be more than that of the O(n) approach and end up running even more slowly! These time estimations have to be taken with several grains of salt in many cases. So using words like "fastest" or "best" is dangerous! SteveBaker (talk) 21:44, 12 December 2013 (UTC)

Here's a rundown:

• If you have an array in sorted order and you're inserting a new item smaller than the existing ones, you have to insert it at the beginning, which means you have to move all the existing items right by one cell, which takes O(n) time since there are n of them.
• When inserting at the end of an array you don't have to move the existing items. But you might not have enough space for another item, in which case you have to allocate a new block of memory and move all the items, and that takes O(n) time. Nevertheless, by being careful about when you do the allocations, you can make the insertion happen in O(1) time "on average" (amortized), even though it sometimes takes longer. This is a subtle point, and you should probably just memorize that appending to an array takes O(1) time (amortized).
  • But that's only if you know that the item belongs at the end. If you have to search for the right location, you would probably use a binary search, which will take O(log n) time.
• To insert anywhere in a doubly linked list, you allocate a new node (constant time) and update 4 pointers (constant time), so it's O(1).
  • But that's only if you know that the item belongs at the beginning or end. If you have to search, the insertion could take O(n) time.
• A balanced tree has a depth of O(log n), and most operations go from the root to a leaf, so they pass through O(log n) nodes and take O(log n) time.
  • But that's only if you don't know that the item belongs at the beginning or end. If you know where to put it, it can be done in O(1) time (amortized).

Basically, these are not terribly well written questions. They're making hidden assumptions about how you're doing the insertions, and the assumptions are inconsistent across the different data types. Your best bet is probably to mindlessly memorize the big-O times they teach you and spit them back out on the test, unfortunately. -- BenRG (talk) 08:37, 13 December 2013 (UTC)

Get thee behind me, SATA!

For a heavy user of Photoshop, would it make sense to invest in a solid state drive that used PCI-Express (such as the RAIDR Express PCIe SSD say), rather than a SATA connected SSD? Hcobb (talk) 19:28, 12 December 2013 (UTC)

When working in Photoshop, are your file sizes in the multi-gigabyte range? --209.203.125.162 (talk) 20:38, 12 December 2013 (UTC)

It's that the user has to work through a camera-load of files at a time to pick the right one to work with and she mostly uses Adobe Lightroom. Hcobb (talk) 21:49, 12 December 2013 (UTC)

I can routinely get 175MB/sec with a two year old Sandisk SATA II SSD module in an US$25 USB 3.0 external case. Faster is always better, but faster is always more expensive. If you can afford the faster PCI express, go for it. --209.203.125.162 (talk) 22:27, 13 December 2013 (UTC)