It depends on the format of the video, since formats such as .mpg are already extremely compressed, which is why you can fit whole videos at great quality on a CD. I believe formats such as .avi and .wmv still have a high compression ratio, but arent as high as mpg.
So instead of compressing it using a program such as winzip (if thats what your using), try getting a video converter that can convert it to .mpg (if it isnt already).